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 ...
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.