Wow, thanks for pointing that out to me. I was not aware of this requirement (when changing location within Russia). I am sure the hotel that will register our visas when we first arrive in St. P. will charge us a fee for this, too.
There may be a further complication in that we are traveling on "tourist" visas, but when we go to Moscow, we will be staying at my friend's company's apartment. Maybe we can call this a "rental" to get around this issue so we do not have any problem registering our visas (again) in that city.
BTW, when I went to the Russian Consulate yesterday here in San Francisco, the fellow who took our applications was actually pleasant. So far, everything is going smoothly, and we should have our visas ready in just ten days!