By default, MSMQ is not fully functional on a Windows CE device.
There is a registry value BinaryEnabled at HKEY_LOCAL_MACHINE\Software\Microsoft\MSMQ\SimpleClient that is set, by default, to "No".
This means that MSMQ (the binary protocol) can receive incoming messages but not send outgoing messages. While you are trying to get your application to work, you might see misleading/bogus/unhelpful messages like "The queue does not exist or you do not have sufficient permissions to perform the operation."
The solutions are either
Make sure you soft-reset afterwards.
There is a similar setting SRMPEnabled for the SRMP protocol.