Edit: They said they checked the spam lists but the ones that I've listed below may be helpful to others. OP might have had an IP previously used by spammers o

Edit: They said they checked the spam lists but the ones that I've listed below may be helpful to others. OP might have had an IP previously used by spammers or in a spam block. (See edit). Important to check the IP before using it if it's been given to you by, say, the VPS Provider or the upstream. To see what, if any, reputation it has. Here are two tools to use: http://multirbl.valli.org/ http://multirbl.valli.org/ http://mxtoolbox.com/SuperTool.aspx http://mxtoolbox.com/SuperTool.aspx And there are a bunch of similar tools.