The issues involved in avoiding mail sent by a server from being marked as spam are incredibly frustrating and convoluted. Here's Jeff Atwood from Coding Horror talking about some steps you can take on your server to make sure mail sent from it gets to it's destination. Gothic, the DC server admin, has been through hell and back dealing with such issues:
Quote
Just because you send an email doesn't mean it will arrive. Not by a long shot. Bear in mind this is email we're talking about. It was never designed to survive a bitter onslaught of criminals and spam, not to mention the explosive, exponential growth it has seen over the last twenty years. Email is a well that has been truly and thoroughly poisoned -- the digital equivalent of a superfund cleanup site. The ecosystem around email is a dank miasma of half-implemented, incompletely supported anti-spam hacks and workarounds.










