Using a hosted mail server with a CNAME that isn't your domain name
tihomir: add TXT SPF Record on your domain that includes your MX recordIN TXT "v=spf1 a:mx1.theemailserversdomain.com a:mx2.theemailserversdomain.com a:mx3.theemailserversdomain.com ~all"and then check out http://old.openspf.org/dns.html
If you want on that site you can look on other domains examples.