How to replace links and embedded image references after migrating of content
Writing a script that does a node_load(), search/replace, and then node_save() is definitely the best way to go about it, and I would argue that it is also the "proper" way to handle the situation.  If you go with this approach, you can refine and/or alter the script each pass to account for differences in the URLs.

In the past, I have


Use rewrites in .htaccess
Done search/replace on a database backup file
Put search/replace in a preprocess_page


to handle the situation, and all of these are not ideal, mainly because of slight variations in URL structure.