I just got a new server and transferred all my customers. All seemed well until they reported their outgoing email was bouncing because it was considered spam. A check at http://www.dnsbl.info/advanced2.asp showed my new server's main IP to be on 11 Spam Lists.
If you have a customer with a lot of email activity, I suggest you check the IP you're going to move them to before moving them. You may be able to avoid several days of Hell.
