はじめに

対象のOSはUAC（ユーザーアカウント制御）が導入されたWindows Vista以降のWindows。実際に確認したのはWindows 7とWindows 8.1のみ。
ローカルとリモートのPCでのユーザーアカウントを一致させておくとか、正しく指定するとか、シャットダウン権限を持っているとか、ファイアウォール設定とかは全部クリアした上での話。

キーワード「shutdown "アクセスが拒否されました。(5)"」での検索からはじめて、分かったこととか最終的にどうしたかとかをまとめておく。

shutdown.exeは"m"オプションでシャットダウン対象のリモートのPCを指定できる。
ただし、UAC（リモートUAC）でリモートからの操作が制限されている場合は次のようにアクセスが拒否されてシャットダウン処理が実行されない。

C:\>shutdown -s -f -t 0 -m \\Foo
Foo: アクセスが拒否されました。(5)

リモートのPCをシャットダウンできるようにする方法

UACを無効（「通知しない」）にする

シャットダウン操作を実行したいリモートのPCのUACを無効（「通知しない」）にする。
当然UACは無効になる。

ローカルセキュリティポリシーの「ユーザーアカウント制御: 管理者承認モードですべての管理者を実行する」を無効にする

シャットダウン操作を実行したいリモートのPCのローカルセキュリティポリシー「ローカルポリシー」－「セキュリティオプション」－「管理者承認モードですべての管理者を実行する」を無効にする。
設定項目の日本語の意味がいまいち分からないけど、たぶんadministratorsグループのすべてのユーザーについて（「特権の昇格を必要とする操作が試みられた場合はすべて、ユーザーに操作の承認を求めるメッセージを表示」せずに）完全な管理者特権で実行することになるのだと思う¹。
とりあえずこの設定をおこなってからadministratorsグループのユーザー（administratorではない）でregedit.exeの起動を試してみたらUACのダイアログが表示されずにレジストリエディタが起動した。
これはadministratorsグループのユーザーについてUACを無効にしていることと同じであるような気がする。

リモートUACを無効にする("LocalAccountTokenFilterPolicy"=dword:00000001)

シャットダウン操作を実行したいリモートのPCのレジストリキー「HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies\System」に、名前が"LocalAccountTokenFilterPolicy"でDWORD値が"1"の値を追加する。
具体的なregファイルは次の通り。

disable-remote-uac.reg

Windows Registry Editor Version 5.00

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies\System]
"LocalAccountTokenFilterPolicy"=dword:00000001

リモートのUACだけが無効になるので通常のUACは設定された通りのまま。

調査の流れ

キーワード「shutdown "アクセスが拒否されました。(5)"」での検索結果から、『shutdownコマンド』で、Windows7をリモートシャットダウンを実行した際に『アクセスが拒否されました（5）』が表示される際の対処法を見つけてリモートUACが原因かもという情報を得た。
それでUACの無効化と「ユーザーアカウント制御: 管理者承認モードですべての管理者を実行する」の無効化を試してみてUACが原因であることが確認できた。
そのあとにキーワード「"リモートUAC"」での検索結果からレジストリの"LocalAccountTokenFilterPolicy"でリモートUACを無効にすることができそうだと知って実際に試してみた²。

まとめ

安全ではないデスクトップに切り替わらない設定でUACの通知を有効にしている程度（デフォルトよりも一段階下）に意識は低いけどUACを無効にする気はないので「リモートUACを無効にする("LocalAccountTokenFilterPolicy"=dword:00000001)」の方法を実施した。
大多数と思われるUACの設定がデフォルトのままの人は同じ方法がいいと思う。

ここまで進めたあとにキーワード「LocalAccountTokenFilterPolicy シャットダウン」で検索してみたところ次のページなどがヒットした。

またSuper Userで検索してみた結果は次の通り。

Posts containing 'localaccounttokenfilterpolicy shutdown' - Super User

ヒット数が少ない。LocalAccountTokenFilterPolicyでリモートUACを無効にするのは好ましくないのか知られていないのか、どっちだ…

参考

注釈

ローカルセキュリティポリシーの「ユーザーアカウント制御: ビルトインAdministratorアカウントのための管理者承認モード」の説明を読んでそう思った ↩
参考にしたのはWindows Vista イメージに UAC のリモートの LocalAccountTokenFilterPolicy のレジストリ設定を変更する方法や [Windows] 管理共有 (C$, D$など) にビルトイン administrator 以外は接続できない（値が間違っている）など ↩