I asked a similar but broader question, and I still need to research and write a complete answer. In the meantime here are some pointers that might help you:
I wrote a set of plugins that resizes all images to the size used in the editor. It works by converting <img src="https://wordpress.stackexchange.com/questions/4984/image.jpg" width="200" height="400"/> to <img src="https://wordpress.stackexchange.com/questions/4984/image-200x400.jpg" width="200" height="400"/> (Resize img tags) and catching and generating those missing intermediate sizes on request (On-Demand Resizer). You should be able to do the first part in bulk, and then let the second plugin handle the new images. It also works with partial information: image-200x.jpg will return a proportionally-resized image 200 pixels wide.
Regenerate Thumbnails indeed re-creates images at different sizes, but I don’t think it also updates your post content to refer to these images? Even worse, if it deletes the old intermediate sizes, your post will still reference the now non-existing image-600x400.jpg instead of image-450x300.jpg.