The whole bit about "searching not sorting" deserves special consideration. If you're like me, you're used to storing different types of email messages in different folders within your email program. You might have a folder for messages from family members, another for messages from work colleagues, and still others for specific projects or events. If you want to look back through the messages from that person or relating to that project/event, all you have to do is open the folder. It's the way we tend to organize things, as witnessed by the huge sales of physical file folders at your local office supply store.
Google, however, has thrown that paradigm out the window. You simply can't create folders in Gmail; your messages are all dumped into the same massive inbox (or, in the case of older messages, archived in the All Mail box). If you want to see all the messages from your Aunt Peg or if you want to read all messages related to a given project, you have to search for them.
(Nitpickers will take this opportunity to remind me that individual messages can be labeled, and that you can assign the same label to all related messages, and that this is kind of sort of like filing your messages. But labeling is only like filing if you happen to throw all your labeled papers into one massive file folder. You still have to search for messages that bear a given label; therefore, the search-not-sort paradigm holds.)
Of course, Google is the king of search, so it should come as no surprise that they try to push the search paradigm in every service they offer. And, in some instances and for some users, that's fine. But not all users think that way, especially when you're looking at an email inbox that over time might hold tens of thousands of individual messages. Do you really want to search through that inbox every time you want to view all messages on a given topic? Wouldn't it be easier to sort the messages by topic beforehand, using the tried and true folder approach?
I have to give Google credit for sticking with their core search paradigm in everything they offer, even if it doesn't always make sense. (It is, after all, how they distinguish themselves from their folder-happy competition at Microsoft.) But, in the case of Gmail, don't count me as a complete fan. I like the massive storage capability, I like the interface, I even like the "conversation" grouping. But I don't like not being able to create and use folders to organize my messages. Would it have killed the Google powers-that-be to let their Gmail customers use folders in addition to search? I simply don't see where not offering a feature (such as folders) gives Gmail a competitive advantage. A best-of-both-worlds approach would have offered the traditional folder paradigm, as well as Gmail's enhanced search functionality.
Are you listening, Google?