I think a plugin that many sites would actually PAY for is something for custom posts and taxonomies like Chris Coyier has at http://digwp.com/2010/10/dynamic-archives/ for blog posts.

For example, in a movie database, show me all the MOVIE (custom post type) instances where the DIRECTOR taxonomy includes Scorcese and the ACTOR taxonomy includes DeNiro.

And an AJAX preview of how many instances to expect (ie “DeNiro (12)”) would be nice, too.

I realize the challenge here is making it flexible for the variety of installs but I suspect it could be done.