Goto www.mail.com. It gives you some choice for the "@____.___" part of your e-mail address. It's pretty good, and I use it for my secure e-mails. Though you will have a bit of a problem with the large amounts of ads and popups that you get from the service, but I find it bearable.
Too bad SEN mail failed. You could've used that instead.
What happened to your other accounts? Did somebody went in and hacked them? Or did you just get kicked out of your accounts for some reason?
I use Yahoo and MSN.
Err... I'm having a problem with one of my friends e-mailing me. Hmm...
Anyway, those are what I use; Yahoo, and MSN.