I'm not sure I understand your solution Alexei... fortunately Yuri Minaev has given me a suggestion which I've used to patch at least two keyword tests.
All I need to do is to use the Code Expression on Run Browser / Navigate / Browser steps that do actuall navigation. All the page objects (and subordinate objects of them) get a wildcard for the domain in the Name Mapping.
So far this seems to be working nicely.
We were considering (since we didn't know how to do things the right way) doing something evil and using "sed" or some other search/replace tool to do bulk replacements on the domain in all the files that TestComplete generates (they seem to be XML files).