I'm hosting my mail on $1 VPS right now. It's hard for me to justify paying more. I hate to setup that mail stuff, it's too tricky and takes a lot of time, but still not worth paying extra.

Pro-tip: do some backups. Cheap VPS can disappear overnight.

This tip is good for almost any service. Gmail could ban you any minute. I doubt that they'll allow to get backups after that.

May be if I'm paying some money to some local company in my city, I can have some confidence, because I can come to their office and yell at them until they return my data to me. But they can just be incompetent and lose it, so even in this case I better do backups.