g1smd - 1:07 pm on Apr 15, 2011 (gmt 0)
This type of question has been asked several times per week, every week for the last 8 years. As such there are a huge number of prior threads with example code and very detailed reasoning for how and why the code is as it is.
The most efficient way will likely be:
1. change all the links on your pages to point to the correct URLs that you want users to see and use. It is suggested that you include an ID number within the new URLs to make the look up much easier.
2. install a rewrite to capture requests for old URLs and internally rewrite to a special script that will examine the request and work out (by way of a database lookup) what the new URL is, and then issue an external 301 redirect to that new URL.
3. install a rewrite that captures requests for new URLs and internally rewrites the request to point to the correct folder and file inside the server to fetch the content.
4. Add a function to the script to check that requests for new URLs are exactly right i.e. that the text within the URL is correct for that ID number, and if it is not then to redirect to the correct URL.