There is another problem, US govt' need to get access all these messages. For example http://en.wikipedia.org/wiki/Hushmail, people seemed to have signed up, but Hushmail was forced to provide plaintext messages to US govt upon request. So they sort of compromised their main selling point.
That is probably the largest problem, you'd be stuck between a rock and a hard place. You either please your security conscious customers or please Uncle Sam. You can't please both.
You're assuming the service has to be located within the US. Why?
With the current legislation trend, eventually un-cooperative or "terrorist friendly" sites would just be filtered out and blocked, so you might have a hard time accessing your email. Some messages might never make it to you.
> US govt can always pressure the local govt
That depends. In some places, the privacy laws are better than in the US. You would just have to choose wisely.That's nice, you still believe that the laws on file actually govern how the country is run.
Bug if you follow e.g. how the spanish SOPA-like was passed, you realize it's all a facade.
I personally have switched between payed google apps for domains and fastmail (those are both $50/yr and under).
https://neomailbox.com/services/secure-email http://www.orangewebsite.com/web_hosting.php