When we don't pay for email, we are at the mercy of free email providers. They can terminate our account for any reason, without no appeal whatsoever. It has happened before.
Email is fundamental, it is the one foundation on top of which we do things on the internet. Forgot password, bookings, registration on a new site - every single one of them is via email. And most of us happily trust Google (or Microsoft etc) with our email, without paying a penny. I'm not saying these companies aren't great, or willfully do something bad with our data (they won't - if anything, gmail is really nice, except for UI) - It is just that they have no incentive to help us when we get in trouble (account getting hacked, for example). After all, they are a business, not charity.
Email is just one example. It surprises me that people wouldn't pay for important things (even when they are cheap) but would happily pay for overpriced coffees, popcorns in theaters (huge rip off) etc. Same with those who buy only "branded" items, even though many times the non-branded items are nearly as good and are cheaper.
However, there is a difference from an organizational pressure perspective: with gmail, I'm not really Google's customer. With hosting, I am the host provider's customer. As a result, the nature of the business relationship is more clearly defined and they have less incentive to play fast-and-loose with the "rules". (Excluding legal mandates, unethical employees, etc. which are an equal exposure either way)
As far as I can tell, paying for your email does not get you any real increase in privacy. Rackspace staff can read your email just as easily as Google staff can read Gmail (it's strictly against company policy in both places, but still technically possible). If the FBI issues a subpoena for your email, both Rackspace and Google will be legally compelled to give it up.