I created a free account with Microsoft and they give you up to 500 email accounts per domain.
https://domains.live.comI had to change the MX & TXT part of the DNS records for the domain.
I would have tried harder to use Google Apps as per dwfreed's suggestions but I had already registered the domain with the Google Apps (for pay) and even after I canceled the Google Apps account they had the domain locked for other uses for 2 weeks. Turns out you must have a minimum of 2 users at $5/month each to use Google Apps for business. I needed an email address on that domain immediately and the Microsoft connection is doing it.