>>HKLM\Software\下を削除するコードを記述したのですが、削除できませんでした。
>>HKCU\Software\Classes\VirtualStore\MACHINE\Software\下を削除するコードでは
>>削除することができました。
それは当然の結果です。
リダイレクトされているので、HKLM\Software\下へは書き込めていません(無いものは消
せない)

>>HKCU\Software\Classes\VirtualStore\MACHINE\Software\下を削除するやり方
>>が正しいのでしょうか？
リダイレクトされることを前提として、書き込み処理と削除処理で別々のツリーを設定
するような処理は控えたほうがいいかと思います。

対応策としては
1、アプリケーションの権限を昇格させる
2、HKCUに書き込むようにする
などがあります。

リダイレクト機能を使うにせよ、HKEY_LOCAL_MACHINEのリダイレクト先は
HKEY_CURRENT_USERの下になってしまうため、
どのユーザからも参照されるためHKEY_LOCAL_MACHINEにという意味合いで使っていた
場合破綻します。

べつにどのユーザからもって意味合いでなければ、仮想化されない
HKEY_CURRENT_USERに書き込むべきでしょう。

そうでなければ、かさのばさんのおっしゃるとおり権限昇格させるなりして、
HKEY_LOCAL_MACHINEにきっちり書き込ませるようにする。

また、iniファイルとかxmlファイルとかにして、共通のアプリケーションデータ
フォルダ(Xpだと、C:\Documents and Settings\All Users\Application Data)
に入れるとかというのもありでしょうか。

参考になったサイト
http://bitwiz.jp/tabid/56/EntryID/19/Default.aspx