There are two ways, one is a bit of a hack and the other one is a bit more complicated.
The first one is to actually make the 404 page a script that does a lookup or whatever you want. If the lookup (on filesystem or in a database for example) fails, then it displays the 404 error page. This is not good because you get all your hits in the error log :-) But I know that even big companies, like Vignette uses this method on their StoryServer and other products.
The second one is the true one. If you run Apache you can use a module called mod_rewrite which rewrites urls. This module is very very very complicated, and at the same time veryveryvery powerful. If you're using IIS then you can find or write your own ISAPI filter. I know the ASP monkeys at our company use a such thing. I dont know what it does but it grabs urls and points them to one file (said in a simple manner).
The functionality is basically the same as the first one.
So, either, hack the 404 page, or find a guru that knows regular expressions and such and code your own mod_rewrite RewriteRules to satisfy what you're trying to achieve.
Good luck!
/Jocke
PS, my the above email might be f**ked due to some of my ISPs DNS problems, but you can reach me at pjs@aspectgrop.co.uk too...