メッセージキューのサービスについて

環境/言語:[windows XP VS2003]
分類:[.NET]

毎回本掲示板にはお世話になっております。
メッセージキュークラスについてお聞きしたくて質問させて頂きます。

メッセージキュー（プライベートキュー）を使用してメッセージの通信を行っています。
キューのパスを.\private$\myqueとしてcreate関数をコールするとExceptionが
発生し、以下のメッセージが出力されてしまいます。

------------------------------------------------------------------------
System.Messaging.MessageQueueException - メッセージ キュー サービスは使用できません。
at System.Messaging.MessageQueue.Create(String path, Boolean transactional)
at System.Messaging.MessageQueue.Create(String path)
-------------------------------------------------------------------------

状況としては、メッセージキューを実装しているEXEをスタートアップに登録
して自動起動するようにしています。再起動を行うと上記の事象が発生します。

Createする前にExistsでキューの存在を確認して、存在しなかったらCreateを
コールして、存在してたらNewしています。

再起動後、キューが存在していると成功し、キューが存在しないと、Createを
コールした時点でExceptionが発生してしまいます。

再起動しているのに.\private$\myqueに既に存在しているのも妙に感じてしまい
ますが、Createを実行してExceptionが発生してしまうのも疑問です。

申し訳御座いませんが、何かわかりましたら教えて頂けると助かります。
よろしくお願い致します。