Product ID duplication

Even though we have an appropriate number of Windows NT licenses, we have several workstations with the same product ID because my predecessor used the same disk and product key to install them. Is there a way to replace duplicated product IDs with unused IDs that should have been used without having to reinstall NT on all the workstations? I tried freeware programs called Keyfinder and EMCO OS License Modifier, but neither one worked. I need to get our licensing legitimate! Thanks