Se você usar o Powershell (como eu disse no meu comentário) tente isto:
Get-ChildItem -path HKLM:\ -Recurse | where { $_.Name -match 'office12'} | Remove-Item -Force
Como alternativa, você pode usar o Regscanner ou, se precisar de mais energia, tente PsExec juntamente com ele.