This is a very interesting question.
First, a clarifying remark. Note that "upper bound on the number of witnesses" is not a property of a computational problem per se, but of a particular verifier used to decide an $NP$ problem, just as an "upper bound on number of states" would not be a property of a problem but of a Turing machine deciding it. So saying "$NP$ problem with upper bound on number of solutions" isn't quite accurate, and if $P = NP$ then every $NP$ problem has a verifier with any number of desired solutions (including zero, and including all possible strings).
So we have to make a definition, to address your question. For $s : {\mathbb N} \rightarrow {\mathbb N}$, let's say an $NP$ problem $L$ "has at most $s(n)$ solutions" if for some constant $c$ there is an $O(n^c)$ time verifier $V$ such that, for every input length $n$ and for every $x \in L$ of length $n$, there are distinct $y_1,\ldots,y_{s(n)}$ of length $n^c$ such that $V(x,y_i)$ accepts for all $i$, and $V(x,y)$ rejects all other $y$ of length $n^c$.
All I think I can say at the moment is this:
- Every $NP$-complete problem I know (defined by some natural verifier) has an obvious corresponding $\#P$-complete counting version (with the same verifier).
- For any $NP$-complete problem defined with a verifier having at most $poly(n)$ solutions (or even $2^{n^{o(1)}}$ solutions) the corresponding counting version probably isn't $\#P$-complete.
More details: Suppose $L$ is $NP$-complete, with a verifier $V$ that has at most $O(n^c)$ solutions. Then the natural counting "decision" version of $L$, which we define as
$Count_L(x) := \text{the number of $y$ such that $V(x,y)$ accepts}$
is computable in $FP^{NP[O(\log n)]}$, that is, a polytime function with $O(\log n)$ queries to $NP$. That is because deciding whether the number of solutions to $x$ is at most $k$ is in $NP$: the witness, if it exists, is simply the number of $y_i$'s making $V$ accept, which we know to be at most $O(n^c)$. Then we can binary search using this $NP$ problem to compute the exact number of solutions to $L$.
Therefore, an $NP$-complete problem of this kind could not be extended to a $\#P$-complete problem in the usual way, unless $\#P \subseteq FP^{NP[O(\log n)]}$. This looks unlikely; the whole polynomial time hierarchy would basically collapse to $P^{NP[O(\log n)]}$.
If you assume $s(n) = 2^{n^{o(1)}}$ in the above, you would still get an unlikely consequence. You would show that $\#P$ can be computed in $2^{n^{o(1)}}$ time with an $NP$ oracle. That's more than enough to prove, for instance, that $EXP^{NP} \neq PP$ and subsequently $EXP^{NP} \not\subset P/poly$. Not that those separations are unlikely, but it seems unlikely they'd be proved by giving a subexp time $NP$-oracle algorithm for the Permanent.
By the way, I have said nothing too insightful here. There is almost certainly an argument like this in the literature.
