Certifying email for more reliable delivery

Is there any effective way to certify a domain name, an email server, an email message, etc so that it will not be bounced as spam?

I've got a short, plain letter .com domain name registered through godaddy (with proxy-registration) that has never been previously owned and has never, to my knowledge, been exploited for sending spam while I've owned it (I have the only user account). But still, some emails - usually critical, initial emails to new customers - are getting dropped, sometimes with no bounce message and nothing in their spam folder.

My mail is hosted through Google Apps where any hosting issue I experience would be multiplied by the number of customers and hopefully addressed or at least known.

I've experienced similar email problems even on cox.net ISP email, but it's really beginning to get on my nerves!

Thanks,

Jason

Answer

One small thing you can do is set up a SPF record.