"Přeinstaloval" znamená že jste provedl čistou instalaci na smazaný disk a nebo jste jen obnovil tovární nastavení ?
Mimochodem spousta nových ntb má "předisntalovány" Office365, takže pokud máte Office 2016 jako trvalou licenci, nemusí tam klíč fungovat.
Jste si opravdu jistý že jste původní Office úplně odstranil? A samozřejmě před opětovnou instalací "Vašich" Office PC restartoval.