http://www.everyone.net/
I used to make decent coin from a giving away free web based e-mails using everyone.net's service. The e-mail's free but you make money from the ad space. That was a long time ago, I'm not sure if they still offer that service.
I doubt you'll have any people paying for e-mail addresses, unless you have some crazy domains.