あくまで推論なんですが。

リモートデスクトップを利用したいのであれば、ユーザーを登録する際、Microsoft Authenticatorによる認証を利用しないほうが良いかもしれない。

TV録画マシンを初期化するにあたって、いつも通りクリーンインストールした後の設定画面でユーザー登録をする際、Microsoftアカウントを用いました。
この時、普段はメールアドレスを入力後、パスワードを聞かれるところで、Microsoft Authenticatorを利用した認証を用いて認証を行いました。

で、普段このマシンはモニターにつながず、作業するときはリモートデスクトップを用いるため、リモートデスクトップを有効にして、ファイアーウォールもリモートデスクトップの設定がされていることを確認したうえで、ユーザー名とパスワード (Microsoftアカウントの)を入力して接続しようとしたところ、

お使いの資格情報は機能しませんでした

なんでやねん。

いくつか設定を確認してみましたが、特に異常はなし。

思い当たる節といえば認証を普段と違う方法で行ったくらいなので、一旦ローカルアカウントに切り替えてから再度Microsoftアカウントに切り替える作業を行いました。
この時Authenticator認証ではなく、パスワード認証を明示的に用いました。

そしたら何事もなかったかのように正常にリモートデスクトップで接続可能に。

可能性としては、パスワード認証ではなくAuthenticatorによる認証を行った場合、ユーザーのパスワードがWindowsに反映されないんじゃないかなぁと。
そんなことあるんかいな(PIN認証でなく通常のパスワード認証をしたいときどうなるんや)という思いはあるんですが、まぁ私の環境ではこういう問題が発生した、ということで。

やはりまずはローカルアカウントを作成してからMicrosoftアカウントを紐づける運用が鉄板なんだなと実感したのでした。