Just a note, the following is a brainstorm session more than a solution. Hopefully it will lead to some feedback and a possible solution in the future.
It seems to me that there should be a way to put the category check higher up, before the theme is selected. As I understand it, currently, the wp-blog-header.php file is responsible for delegating down to the theme's files for a given request. If that request is for a category, then the theme's category php file is loaded (using the standard rules: category-X.php then category.php, etc.).
It seems that that function get_category_template() would be the proper location for this check to happen. Currently, it uses the TEMPLATEPATH variable to check for the existence of and return the appropriate php file to include. If we could refactor that part of the code so that a new function, get_template_path was called to determine the template path, then the entire theme could be modified on a per-category basis.
There appears to already be a get_template_directory function that will do what we want it to do. We just need to parameterize it so that it can vary its return value based on a category id (or any other aribitrary information, for that matter). The problem, as I see it, then becomes 1) replacing all occurances of TEMPLATEPATH with a more dynamic call and 2) ensuring that any sibling HTTP requests get the same template. For example, if the specialized category page requests a themed image, that the image is requested with the appropriate theme, as well. Number one seems rather easy, while two could get hairy as there are numerous places where external links and files may be requested and need to be kept in proper order.
Any ideas for how to accomplish that would be most appreciated as this is something I'm looking to do with my site.