I shall add my tuppence to this thread.
<advert> I should mention work for a company called Memset Ltd. (http://www.memset.com) and we provide both dedicated and virtual machines (based on Xen). Prices are cheaper than that of Bytemark, and we've been in the virtualisation game as long as their have - if not longer. Therefore if there anybody is looking for an alternative to Bytemark or similar, we may be able to help.</advert>
That said, I have my personal email hosted on Google Apps Premier edition (£40 per user per year - I have just a single user account and that suits me fine) and there is no scanning or advertising - and there is some form of telephone and email support if you need it included within that 40 quid too. Why? Pretty much wanted to outsource my own email to somebody as I was working long hours and didn't want to pay too much for my own hosting (I wasn't working in the web hosting industry at the time - so no freebies for me) and Google came along with what was (and still is) a pretty good product for the price. It's not entirely flawless and I generally only stay for the Gmail interface. I have not been able to find any dedicated email client that comes close to it's functionality even when I've attempted to move away from Google.
That said, I have been running a local SMTP server on my own virtual servers and also use them to retrieve and store copies of email from Google - just in case of anything nasty happening to Google (unlikely, but one can never tell these days). Well, it's cheaper (even if I were paying my employers) to archive using my own methods than pay Google's Postini service to archive for me.
Regards,
Martyn