Be sure DNS is correct. You need reverse resolution--it doesn't have to resolve to the name of your host, it just needs to resolve to something. A sane SPF record is necessary to deliver to some hosts. A DomainKey may help deliver to some, though its adoption is still quite low. There are tools on the web to check your DNS zone for you, to be sure things are sane (though some of them are overly critical of unimportant details...but if you get them all right, then you don't have to worry about which ones are important).
Be sure you are sending through a real MTA, rather than using something hacked together in PHP (or whatever language). Every variation from standards is another point or two in the spamminess of your message...Postfix, Sendmail, exim, and qmail can all be configured to strictly adhere to standards. Most scripted mail send tools cannot.
Look at your maillog when testing. You'll know immediately if something didn't make it to the server, and you'll probably know why. The post-processing that leads to "it disappeared" situations usually come from your message looking so spammy that it wasn't even worth saving. If you have a real mail server that can receive as well as send, then you will probably get a bounce. You need to be able to receive those bounces. This isn't optional.