http://www.example.com/example-category/blog-post-permalink/

The blog author did an inconsistent job of adding categories to posts, so while some of them had legitimate categories in their URLS, at least half are “uncategorised”.
I can easily change WordPress to render the URL without the category name (e.g., http://www.example.com/blog-post-permalink/), but I’d like to create a mod_rewrite rule to automatically redirect any requests for the previous format to the new, cleaner one.
How can I use a mod_rewrite recipe to handle this, taking into account that I want to honor requests for the real WordPress directories that are in my webroot?