Suggestions Welcomed - How To Create A Categorized Blog Directory List

I'm new to WPMU and trying to get my head around a couple things. We're building a business directory (of sorts) in a vertical market and intend to use WPMU as our foundation. We'll establish two "member types" (paid / unpaid) and intend to give paid users a blog with a heavily modified admin to enable them to post news articles/press releases, upload product images, etc.

What we're struggling with is how to create a "Category/Subcategory" style listing to categorize the unpaid and paid members across all blogs on our WPMU network.

Each paid member could be listed in multiple categories and each of those categories has multiple subcategories (we're going to limit this - but still will be more than one)

Theoretical Example:

Categories / Subcategories

Pies / Cherry Pie, Apple Pie, Chocolate Pie
Cakes / Chocolate Cake, Angel Food Cake, Devils Food Cake
Cookies / Sugar Cookies, Chocolate Cookie, Shortbread Cookie

Vendor A could be listed in: Pies/Cherry, Pies/Chocolate and Cookies/Sugar
Vendor B could be listed in: Cakes/Chocolate, Cakes/Angel Food and Pies/Apple

The vendor lists need to be presented on a page for each category and each subcategory -- similar to the approach taken by phpMyDirectory.

Just need some strategy suggestions in general on how this might be accomplished with existing plugins or plugin/custom code.

Looking at the Blog Directory Plugin, it seems that it is a one to one relationship -- each blog owner is listed with no real categorization (or if there is any categorization, it's one category per blog)

We want to make WPMU work because we're excited about the downstream possiblities of adding some Buddypress functionality to the site.

Any general guidance would be appreciated -- not asking for free development time, if we need that we'll pay for that when we get there.