Wow ! 306 spam ! I honestly don't think I've gotten that much spam in all my accounts the entire time I've been online (since 2001) ! But then I lead a boring life.
Anyway, and FWIW, just like in my FM account (or any other folder-based system) I have every saved email in some folder (rather than keeping it indefinitely in the inbox), I also make it a habit to label everything I get in Google Apps instead of simply committing it to the abyss, er, archive. I've already read elsewhere (EMD forums) where some people ask, "How can I easily find my email without a label in Gmail ?" It's hard to search for such things, even with Gmail's search capabilities, AFAIK.
I think it would make it a lot easier for people who get tons of email (gigabytes worth) to find something later on if they come up with some label ("Miscellaneous," "Unlabeled," "Everything Else," "The Brig," or whatever). That way one can easily find all these otherwise 'uncategorized' emails without wading through everything in "All Mail."
Yes it can sometimes be tough to find old emails even when you know a unique piece of information that was in the email. I try to narrow the search by using the other persons email address and an approx date range as well. That works ok for me. I don't see how on the surface some "misc" label helps more than the all mail. I agree that using custom labels helps to narrow down the results in the initial search attempts.