こうたご提示のページの「Enable Changing Desktop Background for All Users」.regファイルをダウンロードして実行しましたが、残念ながら状況は変わりませんでした。
手動でレジストリを確認しましたが、NoChangingWallPaperというキーは存在しませんでした。グループポリシーも同様です。
他に、レジストリでWallPaperを検索したところ、HKCU\Software\Microsoft\Windows\CurrentVersion\ThemesにWallpaperSetFromTheme=1という値を見つけました。テーマを変更しようとしても、背景色などは変わりますが、背景画像だけは元のまま(青いバラの画像)です。問題は解決していません。