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.
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.