I'd hesitate to move a mail server to a VPS of any sort. Many of their IPs are blacklisted, as spammers can figure out how to set up a hosting account pretty easily.

Matthew