Hacker News Reader

You have pretty cheap VPS's by OVH (http://www.ovh.ie/vps/vps-classic.xml) and if you ever outgrow their offer you can move to SoYouStart (http://www.soyoustart.com/ie/essential-servers/) which is also a brand by OVH.

TransIP offers VPS with SSD at comparable prices to DO, and more disk space. It's also not an US company, if that makes any difference. No affiliation, just a happy customer.

Regarding blacklists, I run my outbound email through Mandrill. I know it cuts down on the privacy aspect, but I send very few emails anyway compared to what I receive.

I think 20GB is certainly reasonable. I use Thunderbird heavily for three accounts and my profile barely exceeds 3GB.

Why would users need to store all old mail on server? You can auto archive it or simply delete about 95% of mail which you won't ever need later again.