Bulk redirect after permalink change?

Is there a way to get 404 Redirected to automatically redirect posts after we have changed the permalinks to add a directory?

The scenario is that we previously had permalinks at just /%postname%, and now they are /blog/%postname%. Some of the time 404 Redirected catches the change and automatically redirects. But not always.

When a URL comes in, is there a way to tell it to check in the /blog/ directory to see if there’s an exact-match name, and if so redirect there?

The prospect of entering hundreds of blog entries manually is too much. if it’s not possible to bulk-redirect, do you have any suggestions?

Thanks!

http://wordpress.org/extend/plugins/404-redirected/