US の Answers に同じような現象についてのスレッドがありましたので、追記しておきます。
Microsoft Office 2010 and its problems.
Office 2010 asks for the Registration Key every time I restart Windows
こちらのスレッドによると、原因として 1. Damaged Installation、2. Multiple versions、3. Permissions issue が考えられるようです。
解決策として下記がアドバイスされていましたので、もしまだお試しでなければ、試してみてはどうかなと思います。
・ 一度、[管理者として実行] で起動 → 終了 → 普通に起動
こちらの手順をご参考に http://office.microsoft.com/ja-jp/outlook-help/HA010262515.aspx#_Toc260243774
・ もし Office Professional Plus 2010 をお使いの場合は、KB2528748 を適用してみる
Fix it を使うと自動的に修正できます
・ Office 2010 をアンインストールしてから再インストール
こちらも Fix it を使うと自動的にアンインストールできます http://support.microsoft.com/kb/290301
他のバージョンの Office 製品がインストールされている場合は、それも同じくアンインストールしてみてください。
お試しになった結果をお待ちしてます。