Can you elaborate on the kind of key you want to replace? Is it in the form of "absolute path", e.g., HKLM\SOFTWARE\YourSoftware\YourKey, or just a string, ToBeReplaced? In either case, a custom action, most likely in the form of DLL, will be required. The later case will be more involved.
MSI does not natively support "find and replace all" operation. As far as I know in VBScript, there isn't a method to do the same either. The next thing I will suggest is to look into a more full-fledged language like InstallScript or VC++.