Preserving URLs after CMS migration with redirect database and apache http?

view story

http://serverfault.com – We will migrate an entire intranet from one CMS to another. All URLs will change in a non-predictable pattern, but I can capture a file with original,new URLs I can feed into anything. I have hundred thousands of URLs, not just a few hundred. What I would like to do: every URL that is not found (404) should be checked against the database and if a new URL found a 301/308 issued instead. Some trickery to suggest similar pages in the 404 message if the lookup was unsuccessful would be an added bonus. Is that the right approach or should I check redirection first all the time? How would I do t (HowTos)