One problem I've had with VPS is sending email from them. Often the IP addresses get flagged as sources of spam from previous owners - and abusers - of the IPs. If they are so flagged, you will have a heckuva time persuading various list-keeping groups and email providers that your innocent one-a-day emails are not the start of a spam flood of Titanic proportions. Sigh. You are guilty unless you turn yourself inside out to prove yourself innocent.
Have you had them set up rDNS for you yet? If you look at the error codes of the email that gets bounced back you should be able to see if it's actually spam related or if it's just because you haven't set up rDNS - AOL for instance will bounce your emails back if you haven't
"Please open a support ticket at https://billing.chicagovps.net
and state the IP address of the server and what you would like the entry to be set to. Please remember to have a forward DNS entry the same as the reverse entry or we will not set the request."