How about a JavaScript show/hide link for hidden categories (à la collapsible tables)? A <noscript> implementation could reload the page with the 'showhiddencats' parameter set (or something similar).

Well a <noscript/> isn't actually needed.

Stick a link inside the categorylinks, use some css to style and position it in a clean location.

And do the markup something like this:
<a href="/index.php?title=CurrentPage&showhiddencats=1" onclick="javascript: showCategories();return false;">Show Hidden Categories</a>

The javascript intercepts the click, so if the user has JavaScript enabled the AJAX method then would grab the links and show them. (Perhaps some extra code could also alter the location.href if the user's browser does not support AJAX).
And if the user does not have javascript enabled, it behaves like a normal link and reloads the page with the hidden categories.
We could even add something like #catlinks or whatever the id is to the end of that title so that it'll automatically jump back down there when a skin has that id.

As for the Special page. Whether or not a category is created to list hidden categories [[Special:Categories]] should have a 2 or 3 option set to (Show All Categories/Show Visible Categories/Show Hidden Categories) the former two are the most important. As maintenance categories don't have much use on the category list unless the user is looking for them (ie: Someone tracking down a content category has no need to see maintenance categories.) The default setting is up to you.

As for the Hidden categories option, I think that's a good idea to give in any case. Even if we implement something for [[Special:Categories]] it would be good to give the option to let people list those in a real category (Especially if someone also wants to do something with DPL or such).
The category name would be controlled by a MediaWiki message (eg: MediaWiki:Hiddencategories-cat), and that message would be defaulted to '-' which would disable use of the category. (Disabled by default because we don't want a category automatically being used if no-one has bothered to create it. It can come as a surprise to a wiki if MW is automatically inserting a category and they think a user created it and they can't figure out how to delete it)

Fixed in r31262. Using a category to list them means there's no need for an extra index.