Ask HN: Paid Alternatives (for Gmail)?

I was one of the person whose account was accidently reseted by gMail. My account had 10K+ emails over the time period of last five years. I know they will restore it anyways, but still this incident has made me more concerned about having a secure e-mail (I know, no one can beat gmail in ease of use).

What I am looking for is some paid alternative to e-mail. I tried fastmail.fm, and its good enough. I am still not sure about their reliability.

I can afford upto $50 a year, with atleast 1 gb of storage. Reliability is the most important concern.