You won't find ProductCodes or UpgradeCodes in the registry, so searching for them doesn't tell you anything. They are obfuscated. APIs like MsiEnumRelatedProducts (and equivalents) are more accurate.
The general problem may be that the particular ProductCode is already installed in some context that you may not be aware of (per user vs per machine). Strictly speaking, it's the combination of ProductCode and install context that means "already installed". Duplicate PackageCodes can also trigger this error, but that seems unlikely from what you've said.
It's also not clear if you are intending a fresh install or an upgrade of an existing product using major upgrade.
So if you can install it manually but not with AD, then check the context of the AD install and your manual one. If there is a per user install on the system and AD attempts to install another then you'll see this error. In AD, it's something like publishing to the user (per user) vs assigning to the machine (per machine). Vice versa too, you can install per user if there is already a per machine, but AD can't install another per machine if there is already one there. Note that if you're logged on as some other user it will complicate things. There may be a per user install under another account that AD is complaining about, while you and your account can install a per user or per machine.
