I've not used gmail much, but it works out well when I do use it. Think they just opened support for IMAP, which is good for mobile devices.
I personally hate hotmail, yahoo and the other old time email providers. SPAM city in accounts that never actually sent an email to anyone.
Renan's idea works well, I've done it and it is quite handy to have all those accounts. I think dollar for dollar, since you're already paying for another type (or otherwise have it) of Inet connection - that'll be your best bet. Buy a yearly plan or something and it'll probably boil down to paying 3-4 dollars a month for more email accounts then you'll ever use. Additionally you'll get FTP/HTTP space and probably some other goodies.
The best part is you don't really have to be concerned about their web site reliability. You just need steady email service. THEN if they ever piss you off, you just move providers and keep the same email addy.
You could also host all this yourself, but I assume that is not an option.
My '03 Sold.