Not really sure I understand. Are you using your own server to send the mail?
If so there are lots of things to add, like SPF, domain keys, reverse IP etc. HArd to know what to suggest you do until I know what you *have* done. Also, your IP may be blacklisted.
Feel free to email me at damian AT adultmarketing DOT co DOT uk
