Many-body states that do not belong to Fock space? This question may be related with other phys. stackexchange questions: (q1) and (q2).
Fock space is a direct sum of antisymmetrized tensor products of single-particle Hilbert space. In other words, an element of Fock space is a linear combination of Slater determinants with various number of particles.
However, there exists an element of, say, $N$-particle Hilbert space that cannot be expressed by a linear combination of the determinants unless the element consists of spin-orbitals.
According to (q1), Fock space is a special case of many particle Hilbert space, and elements of Fock space describe states in free quantum field theories. I agree with this statement, since a many-body wavefunction that can be expressed by Slater determinants (alternatively, spin-orbitals) implies that each particle has its own wavefunction and behaves independently, crudely speaking.
However, we can express the Coulomb repulsion (two-body interaction) in Fock space, which consists of two creation and two annihilation operators. Using position eigenstates in Fock space (e.g. particles at lattice points), we can even diagonalize it (though the diagonalization would need tremendous amount of calculation). Therefore, Fock space does not have any problem to describe the Coulomb interaction between two particles.
Then, what does the word "free" mean? Fock space would be sufficient to describe $N$-particles in a system with $M$-body interaction, which is far from "free" system. For instance, Fock space formalism has effectively explained superconductivity, antiferromagnetism, etc. induced by strong correlations between electrons...
Well, I am sure that some interaction may require more than just spin-orbitals. I  want to know examples of such interaction.
 A: Probably not a detailed answer, but let's see.
Firstly, you are correct that you can use Fock space to describe interactions, and this is actually mentioned you the (q1) you quoted above. So yes, IF you find a proper basis representing single particle excitations in certain field theories, then you could describe any interaction among them.
The point is, however, what do we mean by a "particle"? The most precise way to define a "particle" in QFT is by finding the poles in the spectrum by somehow calculating Green function "precisely". For example, if you have some non-perturbative approaches for certain QFT, then you can really calculate Green functions and etc. such that, at the end of the day, you could define a "particle" precisely in this field theory, and meanwhile particle number is also well-defined. 
But there are QFT that single particles are not well-defined, neither does particle number operator. The most well-known ones of-course are some CFTs, in which no particles are well-defined. Then in these cases, Fock space, which is expanded by particle-number basis, is not well-defined neither.
