Above #P and counting search problems
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.