Hi - I am starting to work on a similar project for a videographer, who has hundreds of stills representing elements of what is in his videos. Each needs Tto be categorized in multiple ways.
The new WP 3.5 helps in making this possible. Classification systems are now native to WordPress attachments. The regular "category" taxonomy is the standard one, but custom taxonomies can be created and assigned to the "attachments" post type.
I have created a custom hierarchical taxonomy and assign taxonomy terms to media library images. These also appear in the new WP 3.5 media overlay. I found a limitation in the overlay - the Media Library page correctly displays the taxonomy terms hierarchically, like a category box on a Post page. However in the media overlay, they are displayed as a single field, like Tags on a post page, where you type in the name and separate them with commas. That is not acceptable for what I need.
I found a plugin that assists with this:
wordpress.org/extend/plugins/media-categories-2/
The current version in the WP plugin directory (1.4.1) has a few problems in the new media library overlay. However the plugin author has a 1.5 beta which will be ready soon. It correctly displays the hierarchical taxonomy box in the media overlay. As of this morning "Categories" worked correctly but custom taxonomies did not. However he wrote me that he will be fixing that very soon, and intends to release the 1.5 version as quickly as possible.
I found that I can attach the same image to more than one post or page (or custom post type) if I attach it as part of a gallery rather than embedding it in a post/page.
It should now be possible to do wp_query queries on the attachment post type, with taxonomy of xxx and taxonomy terms of xxx and yyy. That handles displaying the images as required.
This might be a workable approach for your needs.