I've been considering this, my main problem is that my cash flow is fairly spotty at times for a dedicated server and I would prefer not to have to worry about the security of my box, uptime and the like.
A guide I mentioned earlier (http://flurdy.com/docs/postfix/index.html) shows how to set this up on Amazon EC2. If you haven't partaken, Amazon is still giving away a free-for-a-year tier of EC2.
When I consider targeted advertising and the sheer amount of data that I've pumped into Google services over the years it's scary to see how accurate of a picture advertisers and co have of me.
Why does this scare you though? I am curious as to why people are so afraid of advertisers seeing their interests. Personally, I don't care if I get served targeted ads, is that really going to harm me?
I use google extensively, gmail for years, google docs, etc. I must have clicked the right things in the privacy checkboxes since when I go to that "what does google think of you" page, it just says it "does not have enough data".