Thanks. Just found these comment by the author on the Regenerate Thumbnails homepage
Posts contain hard-coded references to specific thumbnail sizes. My plugin does not currently go through all of your posts and update those references.
Featured image, gallery thumbnails, and other dynamically generated HTML is what gets affected by this plugin.
If you insert a medium sized image into a post, the width/height will be hard-coded into the HTML. Changing settings will not affect that post. My plugin (currently) does not touch posts or anything else either — it only creates thumbnail images.
I have been playing around with some code that will go through all of your posts and update the HTML for inserted images though (i.e. so when you change settings, you can update the sizes in posts too). Perhaps I should polish it and release it.
I'm guessing there's no easy way to do this then? Search and replace could work but only if all the image sizes were the same.
Just wondering what massive sites with thousands of posts and images do when they change their layout?