I haven't had problems with Gmail losing my mail, but I've found it hard to sift through conversations to find what I need. Search doesn't always help with that.

Maybe I'm old, but I still like Yahoo! Mail's old web 1.0 interface. Maybe that's just because I know all the quirks after years, but I can find what I need quickly and store messages easily.