MSMQ needs the secure channel to be open.

There's a new KB article and hotfix that you may have missed as it is not an MSMQ bug.

936455 Error message when a domain-joined Windows XP Professional client computer establishes a security channel to a domain controller server computer that is then restarted: "STATUS_ACCESS_DENIED"

The scenario is reasonably simple. A Windows XP client has queues on it that your application (running elsewhere) wants to send to. The client has a secure channel to a Domain Controller but the DC is subsequently rebooted. When the application tries to send messages, they will be rejected "Access Denied" as the Netlogon authentication data has become stale. If you then browse to the client using Windows Explorer (or perform some other type of interactive network communication), the secure channel is re-established and new messages can be sent.

The fix is in LSASRV.DLL so the problem appears as a Windows XP problem, rather than MSMQ. Windows 2003 doesn't have the same issue as the problem was spotted and cleaned up during that product's develpment.