Redirecting URL without postID

I have a news blog, skymania.com, with more than 800 posts. Last year, to suit the requirements to get accepted as a Google News source, I adapted the permalink structure of domainname+postname to include also the post ID number.

This works well within the normal operation of the database. However, I have hundred of posts with links in the stories to “domainname/postname” which now take take readers to a 404 not found page. I have included a Google search box in this which is automatically filled with the fault link and which they can then use to find the correct link in a flash. However, is there a way to get WordPress to do this automatically, i.e. read the URL without the post ID and then find the post with the post ID?

e.g. http://www.skymania.com/wp/2008/04/here-comes-solar-tsunami.html
needs to redirect to
http://www.skymania.com/wp/2008/04/here-comes-solar-tsunami.html/578/

Paul