Originally Posted by ATNotts
The best suggestion we had is to pay for a Static IP address for our e-mails.
The best suggestion is probably to stop your sever sending out spam.
There are lots of blacklists out there, and if your server is sending out spam you'll end up on all of them in due course, regardless of whether you have a static or dynamic IP address. And the longer your server is spewing out spam the harder it will be to get off the blacklists once you've fixed it.
It might not be that your mail server is misconfigured, to be an open relay or in any other way. It might be that one or more machines in your office has been turned into a zombie and is spewing out spam via your perfectly corrrectly configured mail server.
"One of the machines in your office" could of course be a laptop that was plugged in to your network temporarily ... or, if your office has a wireless network that isn't properly secured, "one of the machines in your office" could in fact be a laptop in a passing car.