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://mxtoolbox.com/SuperTool.aspx
And there are a bunch of similar tools.