Don't host your email on just any old cheap VPS. Many VPS providers have bad reputations for not policing spam senders, and as a consequence large email services like gmail often block whole ip ranges that belong to these VPS providers.
At least make sure the IP address isn't blacklisted before buying it.