I have the same problem with my email addresses being blacklisted, as the address is used by spammers on a regular basis. I tried to appeal to the blacklisting companies and got nowhere. The biggest surprise I got a while back was an email from myself selling drugs!
I have never spammed myself and hate with avengence (understandably) those who do. Yet suffer the consequences of blacklisting as a result. I get round the problem by using a hotmail account to email those whose ISP reject my emails.
However that said, all my sites rank well in the search engines. Interesting that moving servers could cure the problem, but I suspect the ranking will drop dramatically just because the server has been changed.