If the function f is in #P, then given an input string x of some length N, the value f(x) is a nonnegative number bounded by $2^{poly(N)}$. (This follows from the definition, in terms of number of accepting paths of an NP verifier.)
This means that many functions f lie outside of #P for uninteresting reasons---either because f is negative, or, in the case you mention, because the function grows faster than $2^{poly(N)}$. But for the $n$-queens problem as modeled in the paper, this is just an artifact of the authors' decision to let the input value $n$ be encoded in binary. If the expected input was the unary string $1^n$, then $f(1^n) :=$ (number of valid $n$-queen configurations) would certainly be in #P, by a simple NP verifier that checks validity of a given configuration.
If you want to explore some functions that (conjecturally) lie outside of #P for more interesting reasons, consider e.g. these:
- UNSAT: $f(\psi) := 1$ if $\psi$ is an unsatisfiable Boolean formula, otherwise $f(\psi) := 0$. This function is not in #P, unless NP = coNP. It is probably not in the more general counting class GapP, either; that is, UNSAT is probably not the difference f - g of two #P functions. However, it lies in the more general counting complexity class $P^{\# P}$, which in fact contains the entire Polynomial Hierarchy by Toda's theorem.
You might not like that example because it is not a natural "counting problem". But the next two will be:
$f(\psi(x, y)) :=$ the number of assignments to $x$ such that the Boolean formula $\psi(x, \cdot)$ is satisfiable for some setting to $y$.
$f(\psi(x, y)) :=$ the number of $x$ such that, for at least half of all $y$, $\psi(x, y) = 1$.
The latter two problems are not known to be efficiently computable even with oracle access to #P. However, they are computable within the so-called "counting hierarchy". For some more natural problems classified within this class, see e.g. this recent paper.
Counting Nash equilibria is apparently #P-hard, see here. Also, even problems where the search problem is easy can be #P hard to count, e.g. counting perfect matchings.
