One little trick that I rarely see mentioned for working around the negative or neutral reputation your MTA's IP might have is that you can route your outgoing emails through another MTA that has a higher reputation. For example route them through smtp.gmail.com (or for other options see https://support.google.com/a/answer/176600?hl=en ). It does not mean you have to use Gmail. It does not mean you have to change you…
Huh..never thought of this. I run my own e-mail server on a Linode. I have constant trouble not being classified as spam. I did a whole post on it: http://penguindreams.org/blog/how-google-and-microsoft-made-... The sad reality is, I'm thinking of moving my e-mail back to someone else. It might be Fastmail, might be Amazon. Running my own e-mail server is a pain and I hate having to send people a message on Facebook…
I find it hard to believe that you get classified as spam for no good reason, unless perhaps that Linode / Digital Ocean are known for hosting so much garbage and people can be tempted to outright block them, but I doubt Gmail does that?