.htaccess wildcard redirect 301

I don't know what exactly defines a "maintenance nightmare" in your book, but you could try to go with a dynamic rewriting map in apache:

RewriteEngine on
RewriteMap    vanity-map       prg:/path/to/vanity.pl
RewriteRule   ^/(.*)/(.*)$  /${vanity-map:$1}/$2

vanity.pl could could be a simple perl script (don't forget to set $| = 1;) which gets the first part of the request URL (as outlined above) on STDIN and is supposed to rewrite that - e.g. by querying a database.

Now, that just leaves the frontend. I'm an inexperienced Ruby on Rails programmer (it's just a spare time activity), but I think, if it doesn't need to look pretty, even I could write an application that authenticates a user, lets him create a rewriting and shows that up for approval to some IT guys/$WHATEVER in much less than a week, so I don't think any real programmer would have a problem doing that in a few hours. Depending on the database, there might even be frontends readily available which will do the job with only a little customization (php*admin comes to my mind).

This way, you get all the flexibility of a database approach paired with a central source for all redirections. As long as the database's index on the URL part fits in your servers memory, you won't even have to worry about performance.

RuslanY's Blog has a great post that describes how to do this with the IIS rewriter.

I will quote his Tip #3 :-

Very often you may have one IIS web site that uses several different host names. The most common example is when a site can be accessed via http://www.yoursitename.com and via http://yoursitename.com. Or, perhaps, you have recently changed you domain name from oldsitename.com to newsitename.com and you want your visitors to use new domain name when bookmarking links to your site. A very simple redirect rule will take care of that: view plaincopy to clipboardprint?

<rule name="Canonical Host Name" stopProcessing="true">
    <match url="(.*)" />
    <conditions>
        <add input="{HTTP_HOST}" negate="true" pattern="^ruslany\.net$" />
    </conditions>
    <action type="Redirect" url="http://ruslany.net/{R:1}" 
            redirectType="Permanent" />
</rule>

To see an example of how that works try browsing to http://www.ruslany.net/2008/10/aspnet-postbacks-and-url-rewriting/. You will see in the browser’s address bar that “www” is removed from the domain name.