"Sitemap" view for Document Library?

Does anyone know of a webpart out there that offers "sitemap-like" view of a document library?
Here's the situation:

I've got a legacy file server which contains a plethora of documents, in a folder structure separated by department at the top level. For the most part, you have to go 3 or 4 levels deep in folders before you get to the actual documents (typical of an organization's file servers, eh?).
After cleaning out the obsolete folders and documents as best we could, we imported the file server docs into a number of SP2007 document libraries, one for each department. Thus, what I ended up with were document libraries which still have folders for the first few levels.

I'd like to display the contents of one of the document libraries in more of a "sitemap" type view, whereby the top two levels of folders show up as links and sub-links on a page. The links then should bring you directly to that particular location within the document library. Something liike this:

Administration

Administration Policies

Collection Manual

Case Management

Service Policies

Case Sheets

I played around with the out-of-the-box customization of views of SP document libraries, but it all seems to concentrate on a "datasheet" type view.

I also saw a "Site Hierarchy" section in the left nav of SP2007. However, this was more of a Tree view, and forced the user to expand each folder within the Doc library. I would like to display in more of a "Sitemap" type view, showing only the first two levels.

Would this be a job for a custom webpart?
If there's another way, I'm all ears.
I haven't done development in SP2007 yet, but I'm not afraid of developing custom webparts.
I'd imagine something which uses some exposed SP web services to navigate a Document Library structure, perhaps control the output to the page using XSLT? Any other ideas?

Thanks,
Mike

P.S. I have a nagging feeling that in approaching the problem this way, we're missing the recommended solution in SP2007, which would be to not worry about the folder structure, and rather use SP's Search capabilities to get the user to locate the documents he/she is looking for. I'm investigating this "Site map" type thing because my end users are resistant to change, and they like their little sitemap view of documents that someone created for them in straight HTML a long time ago.

[3368 byte] By [TheLink] at [2008-1-1]