I don't think those have auto-signup...or do they?
I use everyone.net for three different sites. It's like Bigmailbox, only much, much, MUCH more reliable with no ads at all. You just reset your MX record.
There is a charge that varies depending on what plan you get. I generally use the $10 month plan, you get 100 6meg boxes. You can rotate ads and make that much or more back to cover the $10. Completely customize, users can auto-signup like Hotmail or Yahoo, ect, ect... A lot of my users say they've quit using their other email accounts because they like it so much.
They also have a thing where users can upgrade accounts to paid and you get a commission or share ad space 50/50 if you have the traffic and get rid of your fee alltogether. You can check it out yourself
http://www.everyone.net