you can host the domain mail on something like google apps for about $30 a year per user or microsoft's outlook.com service for free
you only need a company to do the domain purchase and dns hosting - i have used zimhosts before and they are a little slow but very reliable from my experience