What I have is:
[Steps 1 ... 10]
I'd suggest some slight changes. First, step 9 should actually be step 4.5 . RM&C won't do anything if you don't select files first.
Then, after step 8, but before step 10, I'd suggest that you look at the RM&C Preview Window. It's going to show you what it will do before it does it. Make sure that it looks correct before you press OK. If it doesn't look OK, you can change your Find and Replace parameters, or something else, or start over.
One question I have is: what will MC do after step 4, when it can't find any of the media files the newly restored library points to?
Good question. You should turn off auto import as soon as you possibly can after doing your library restore. Tools > Options > Library & Folders > run auto import in background > (uncheck)
Part of auto import is a setting called "fix broken links", which *might* be set to remove missing files. So if you turn off auto import, you'll protect against this happening. Otherwise, MC won't do anything other than show you a red minus sign (-) next to each file and refuse to play it because it can't find the file.
Then, another question: is there a better (easier or safer) way to do this?
You've actually done a remarkably good job at outlining the proper procedure. This is the fastest, best way I personally know of doing this job. Once you've done it a time or two, you will probably find it to be relatively easy and quick.
The RM&C tool is one of MC's best features. It lets you do things that other media managers just can't do. Once you understand it's power, you'll be able to really control everything about your file layout, including these types of "I want to move some or all of my stuff" jobs.
Good luck and let us know how you do!
Brian.