That market does exist today, Fastmail.fm is only one example I can think of off the top of my head (I surely got the ofs and offs wrong). I talk about them so much that I sometimes feel like a marketing goon ...
They're not a viable privacy option. And it has little to do with their ethics: they are still vulnerable to subpoenas, many of their users don't even live in the same country…
The only viable privacy option is to host your mail at home. It doesn't have to be difficult. We "just" need a suitably tailored GNU/Linux distribution in a Sheeva Plug, or Raspberry Pi, that you just plug-in, then use as a web service. (Just one snag: your ISP must allow you to send and receive e-mail: many close off port 25, and some even ban home servers.)
Now to get your email, they need a search warrant and someone to knock on your door, which is inconvenient and costly.
