Gmail: If you have to use it, because you don't find anything anymore...
...then you might have done something wrong. That's my opinion.
I mean: Who the hell gives his relevant mails to Yahoo, Google or Hotmail? I'm getting the relevant ones traditionally via my own personal server. I download them via POP3 or leave them where they are and use them via IMAP. In my mail-client (i.e. Outlook) I'm able to filter those mails. I can sort them based on rules or whatever. So, please: What do I need Gmail for? I would use it as some sort of mass-storage for my mails. But then I know, where to find which mail, because I'm always sorting them.
So, again: What do I need Gmail for? Where's my advance when giving Google the right to "read" or at least analyze my own private mails and to place ads in or next to them based on the textual context? I feel I will loose privacy when organizing my mail with Gmail. So I won't use it. But I'm happy with the 2 GB of storage MSN offers me.
And because of this: It's all about size. :-)