Office アプリの設定、プロダクト キーの引き換え、ライセンス認証を行うことに関する Microsoft 365 のプロセス。
SSD換装で別PCと認識されたとしても、パッケージ版をこれまで1台だけの使用なので2台目となるはずですから、認証されないのはおかしいです。
既に2台で使用していて、1台が故障してアンインストールできずに、別のPCに買い替えで実質3台目となるようなケースでも、電話による認証で使用可能になります。
認証窓口で理由を説明すれば、認証作業ができます。
Hebikuzure さんの回答にある認証窓口のほうに、直接問い合わせが良いかもしれません。
パッケージ版の再インストールは、初回のインストールで使用した Microsoft アカウントで、サービスとサブスクリプションにサインインして、購入済みの製品の「インストールする」から行います。
Microsoft アカウント | サービスとサブスクリプション
下記のアンインストールサポートツールを使用して完全に削除してから、再インストールを行っても、同じように台数超過となって認証されないでしょうか。
ツールを使用してのアンインストールは、多少時間がかかります。
永続版の場合は、何台のデバイスで使用していることになっているか、といった情報などを参照できる場所がありません。