Google is now offering a FREE service called “Gmail for your domain“, in which they will provide Gmail service to a domain, any domain, YOUR DOMAIN!
When you logon to Gmail you will use a your company’s domain name instead of the Gmail.com domain, and all the e-mail service will be hosted on Google’s servers.
As with Gmail, users will be able to get 2 GB of storage space, plus the advanced features of normal Gmail services, such as calendaring (some features are integrated into Outlook!!!), searching, spam filtering and user interface that is similar to the normal Gmail view.
Administrators can easily manage user accounts, aliases as well as mailing lists. And all users on your domain will be allowed to get the Gmail-powered web mail account, along with some customizable features such as a company logo and more.
Note that you still need to provide proof of owning the domain, and also the ability to make changes to your MX Records in order to start the mail flow.
Microsoft‘s equivalent is called “Windows Live Custom Domains“, read more about it on the Host your Domain E-mail with Windows Live Custom Domains article.