That's because people are idiots. Not only would a European-based competitor NOT prevent the NSA and GCHQ from getting at your data, it's not going to prevent any other agency from getting at it either.
I think that's a bold claim. Remember that when GCHQ wanted to spy on phone calls from the Middle East, they didn't do it by serving Belgacom with some dubious order from a bogus court. No such courts exist in Europe, at least as far as I know. They did it by hacking Belgacom directly and then they got caught when the telco went looking for them (and presumably evicted).
The UK has some pretty crap laws when it comes to surveillance, largely a hangover from the IRA era (which was a way scarier terrorist group than al-Qaeda, so it's somewhat understandable). The "9 hours at the border" thing comes from that time, it predates 9/11 actually. However the rest of Europe, not so much.
With regards to the solutions, I guess some companies will do exactly as you suggest and in source, or at least partially in-source private data. But that's a giant pain in the ass. Expect to see some novel and innovative approaches to squaring this circle in the coming years - cryptographers have spent a lot of time finding ways to do computation in the cloud over encrypted data. Perhaps they will finally see some of it get used.