OK, finalmente encontrei uma referência para fazer a criptografia não-Active Directory MSMQ. Aqui está o link. Não é difícil quando você encontra a documentação!
É assim que você usa a criptografia de mensagens com o MSMQ, mas não usa o Active Directory.
Do TFA:
Demonstrates
The client encrypts the message using the public key of the service and signs the message using its own certificate. The service reading the message from the queue authenticates the client certificate with the certificate in its trusted people store. It then decrypts the message and dispatches the message to the service operation.
Because the Windows Communication Foundation (WCF) message is carried as a payload in the body of the MSMQ message, the body remains encrypted in the MSMQ store. This secures the message from unwanted disclosure of the message. Note that MSMQ itself is not aware whether the message it is carrying is encrypted.
The sample demonstrates how mutual authentication at the message level can be used with MSMQ. The certificates are exchanged out-of-band. This is always the case with queued application because the service and the client do not have to be up and running at the same time.
Description The sample client and service code are the same as the Transacted MSMQ Binding sample with one difference. The operation contract is annotated with protection level, which suggests that the message must be signed and encrypted.