I have my fonts organized in multiple ways (even though FontAgentPro -- the best resource IMHO -- is not the easiest way to do this):
First, in Libraries according to origin (eg Adobe, AgfaType, MonoType, etc. etc.) -- I do this when importing them.
Second, in Sets -- Display, Serif, Sans, Slab-serif, Script, Pi, in the way FontShop's FontBook does (you do need a reference!) -- and also in Sets for each Client or Project.
It took me a couple of weeks to get everything in shape, but then I had a fifteen year legacy (I had to troubleshoot a lot of fonts).
You may have an easier job.

I just cleaned up my personal (vastly simpler) type collection recently, so maybe my own process will be helpful.

My goal was to end up with a system on which I could trace the origin of every font installed, with the aim of having all of my type legal, and know where to find all of the licenses and EULAs for my type. My first step was to blow away my existing FontAgent Pro and FontReserve archives (yes, I own licenses to both programs, having licensed FontAgent Pro when I finally ran out of patience for dealing with Font Reserve's many bugs and its glacial release schedule): they were both at around 17,000 fonts that I'd acquired from various sources over the years. Not only did I have many, many unlicensed fonts, both FontAgent Pro and Font Reserve ran incredibly slowly and were more or less unusable and unnavigable. So boom, deleted that and my machine was instantly a lot more responsive (FontAgent Activator was a huge pig).

Then I created a new set of three folders inside my top-level fonts folder:

1 free / "free" fonts
2 licensed non-free fonts
3 unlicensed non-free fonts

Within those folders, I created a folder for each typeface or type family, following a strict naming convention of foundry, then family name, then the formats contained within the folder: "Linotype Neue Hammer Unziale ot", "MADtype Brauhaus t1", etc.

This list gets quite long, but it makes it really easy to find everything, either via scanning the list or using "Find..." on the fonts folder. This, in turn, will help me keep my FontAgent Pro installation relatively slim, because I only import fonts into FontAgent when I need them. I've also gotten in the habit of creating a separate library (something FontAgent Pro makes easy) for job fonts (i.e. fonts provided by customers to be deinstalled at the end of a contract).

I won't deny that there are a few warezed fonts still floating around my system (see folder 3, above), but those that I do have I keep around for short periods of time, and my strict policy is to not use anything in even personal projects unless I have a license for it. (As a brief aside, I'm really happy with this policy, as it's forced me to be more deliberate in general about which type I use, and I definitely attach more value to individual fonts than I did before. This should be obvious, but most of the designers I know come from the "more is always better" school, and many, if not most, of the designers I know are still more or less amoral when it comes to font piracy.)

I think you might want to create a fourth folder for fonts of unknown or dubious provenance, and gradually sort it over into the other three folders over time. I'd also create a fifth folder in which to keep sets of fonts that are sent in for specific jobs, and try to keep those fonts out of the other four folders, and try to keep them organized into sets in your font manager so you can clean them out at the end of a job.

I've done service bureau work before, and I know what a nightmare it is trying to stay on top of everything that comes in for jobs. I think the key is to not try and do everything at once, and to set up structures that make it easy to improve organization over time.

Also, if you can, invest in the workgroup version of your font manager. Having one repository of fonts will make your life a lot easier in the long run, even though client-server font management brings some unavoidable maintenance and troubleshooting with it (in particular, corrupt fonts on the server can cause massive headaches for everyone, and font caches need to be cleaned out with alarming regularity).

As a final note, both FontAgent Pro and FontDoctor are OK at verifying fonts, but both of them have trouble with false positives (marking fonts as bad or missing PostScript / bitmap versions when in fact they work fine in Mac OS X) and false negatives (failing to notice that a font is corrupted). I'd suggest buying and using them both. Also, I don't like how either one automatically organize fonts, mostly because they're dependent on the metainformation stored inside the fonts, and foundries are incredibly unreliable about getting this information in there completely and correctly.