普通に起動したアプリではHKEY_CLASSES_ROOT以下のエントリーなどに
書き込めないという意味でしょうか？

これはWindowsのセキュリティ仕様ですのでどうしようもないと思います。

一般的な対策としては、レジストリに対してそのような書き込みを行う
必要のあるアプリは、管理者権限モードで起動させるようなマニフェストを
追加しておくのがいいと思います。

このようにすると、アプリの起動時に自動的にUACのダイアログが表示されて
権限の昇格が求められるようになります。ユーザーが許可して
アプリを起動すれば、レジストリの書き換えも可能になります。

以下のサイトが参考になると思います。
http://www.atmarkit.co.jp/fdotnet/dotnettips/958uacmanifest/uacmanifest.html

「requireAdministrator」を指定すれば大丈夫だと思います。

また、VS2010（VS2008は未確認です）であれば、マニフェストファイルを
直接編集しなくても、プロジェクトの管理ダイアログから設定できます。

レジストリに書き込むのが必須なのかと言う部分も
考慮した方が良さそうな気がします。

流れとしてはアプリの設定情報の保持にレジストリを
使わない方向になっていると思うので方法論を変える
方向で考えた方が良いのではないかなと。

.NET Frameworkでは設定情報はxmlファイル形式で
書き込み権がある場所に保存する事になっているので
そちらの方式を参考にした方が良いかもしれません。

レジストリに登録しないと仕組み上動かないと言う話なら
仕方ないと思いますけれど。

Win7 であれば管理者権限でなくても HKEY_CLASSES_ROOT には書き込めるはずです。
HKEY_CLASSES_ROOT とは実体を持たない仮想キーで、実体は HKEY_CURRENT_USER \
Software \ Classes と HKEY_LOCAL_MACHINE \ Software \ Classes がマージされたも
のです。
管理者権限でなければ HKCU の方に書き込まれます。

HKCU 以下には通常ユーザー権限でも書き込み可能です。

ということは、管理者権限でなければ書き込めないキーとは HKLM ということになるわ
けですが（まさか HKEY_USERS ではないでしょう）。
アプリを通常運用していて HKLM に書き込む必要があることはそうそうないはずです。
あるとすれば、一般的にはインストール時くらいのもので、インストーラは管理者権限
で実行するのが普通なので問題になりません。

いったいどういうシナリオで、どこのキーに書き込もうとしているのでしょうか？

記述したかったレジストリは、
HKEY_LOCAL_MACHINE
部分です。
環境設定をレジストリで
強制的に行おうという考えです。

単に管理者権限での実行の問題でした。
「requireAdministrator」
の設定で解決しました。

ありがとうございました。