購入時のプロダクトキーですが、初回のセットアップを行うときにマイアカウントページを作成するために使用し、セットアップが完了すると Microsoft アカウントと紐づけされます。
マイアカウントページには、購入した製品が登録されて、インストールするための別のプロダクトキーが作成され参照することができるようになっています。
再インストールを行う場合には、初回のセットアップで使用した Microsoft アカウントでマイアカウントページにアクセスをして再インストールをするようになっており、アカウントと紐づけがされているのでプロダクトキーを指定することは必要ありません。
原因はわかりませんが、IE などの Web ブラウザーを開いて Microsoft アカウントでマイアカウントページ(個人用アカウント)にアクセスができるようであれば、表示される製品のプロダクトキーを確認し、それを指定してみてはどうでしょうか。
マイアカウントページ: http://www.office.com/myaccount/
昨日、新規購入の PC に付属の Office Premium の初回のセットアップ時に、Microsoft アカウントでサインインした直後に同様のメッセージが表示されて、先に進めなくなったとの質問がありました。
現状、このメッセージに対しての対処方法が不明なので、サポート窓口 への問い合わせを勧めました。
「Webページへのナビゲーションは取り消されました」と表示され Office のセットアップが正常にできない