Why are interacting electron systems hard to solve? It is often said that interacting electron systems (say on a lattice, like the Hubbard model for example) are difficult to solve because of the exponential size of the Hilbert space. 
However, I am not sure I find this argument very compelling. Non-interacting systems live in the same Hilbert space and yet are easily solved. There are also cases of interacting models that can be solved and it is not by brute force, I'm thinking about the Bethe ansatz for example.
I can also quote this interesting paper : Quantum Simulation of Time-Dependent Hamiltonians and the Convenient Illusion of Hilbert Space:

As an application, we showed that the set of quantum states that can be reached from a product state with a polynomial-time evolution of an arbitrary time-dependent quantum Hamiltonian is an exponentially small fraction of the Hilbert space. This means that the vast majority of quantum states in a many-body system are unphysical, as they cannot be reached in any reasonable time. As a con- sequence, all physical states live on a tiny submanifold, and that manifold can easily be parametrized by all poly-sized quantum circuits.

So, are these models difficult to solve because no one has found a suitable ansatz yet, or is there a fundamental reason to give up the hope of finding such an ansatz? Or at least a more convincing argument than the size of the Hilbert space?
Related : Proving that the electronic Schrödinger equation has no closed analytic solutions for >1 electron
 A: The fact that weakly-interacting systems are easy to solve is a red herring. Those systems do indeed live in the same Hilbert space, but they can be confined to an excellent approximation to a very 'thin', and very well-characterized, slice of that space, i.e. to the non-interacting ground state in direct sum with only a few variations of single-particle excitations, without involving the full brunt of the exponential sea of entangled states.
Your second argument, on the other hand, is much more compelling, and it cannot be easily set aside. However, it is only an argument on the lowest possible bound on the computational complexity of algorithms to solve for the eigenstates of local hamiltonians ─ if we are clever enough to find those algorithms. 
As an example, the computational difficulty of preparing entangled states is often used as a suggested justification for why Matrix Product States, and similar representations, have a good shot at being able to capture most of the fraction of Hilbert space that the system actually occupies while using only polynomial resources.
However, just because there are potentially polynomial-complexity algorithms somewhere out there in algorithm-space that can effectively capture the nontrivial submanifold of the exponential Hilbert space that's occupied by the ground states of local hamiltonians ─ that doesn't make the problem easy to solve, because you need to put in the human intellectual and conceptual work to understand how to get those algorithms and what makes them tick. 
And, unlike the weakly-interacting case, you can't just make a blind guess at the subspace of interest and trundle off in that direction hoping that brute force will solve everything, because that brute-force approach would require you to play on a sandbox that was exponentially larger than the slice of interest, and that exponential size completely trumps your pretended brute force.
A: If every electron lives in its own Hilbert space $\mathcal{H}_e$ of size $D$, and we have $N$ electrons, then the total many-body system lives indeed in an exponentially bigger space $\mathcal{H}_s=\mathcal{H}_e^{\otimes N}$ of size $D^N$, which becomes rapidly intractible.
The surprising thing is not that interacting systems are hard to solve, but rather that non-interacting systems are easy to solve. For non-interacting systems, the problem factorizes entirely, all copies of $\mathcal{H}_e$ are truly independent and can be solved separately (or in fact, one of them is enough if they are identical), so that the exponential complexity of $\mathcal{H}_s$ is not important. 
If there is weak interaction, a factorization can be made aproximately (Hartree, Gutzwiller, Mean-field ansatzes). A good example is the Gross-pitaevskii equation which assumes a problem factorized for individual particles. To get improvement, one should add Bogoliubov fluctuations. More generally, the systematic way to do this is a cumulant expansion of correlations (see also: BBGKY hierarchy ) that must be truncated. For a non-interacting system, there are no correlations.
