WCF MSMQ DllNotFoundException

I am trying to access a remote WCF service (using netMsmqBinding) hosted in a windows service and am getting the error:

Message: System.TypeInitializationException: The type initializer for 'System.ServiceModel.Channels.Msmq' threw an exception. ---> System.DllNotFoundException:     Unable to load DLL 'mqrt.dll': A dynamic link library (DLL) initialization routine failed. (Exception from HRESULT: 0x8007045A)
at System.ServiceModel.Channels.UnsafeNativeMethods.MQGetPrivateComputerInformation(String computerName, IntPtr properties)

I have read that this error may come up if msmq is not installed, but msmq is not supposed to be installed on the local machine... it is installed on the remote machine it is trying to talk to.

What else can cause this?

Any machine wishing to participate in the transmission of messages requires MSMQ to be installed.

This is because MSMQ uses a messaging pattern called Store and forward, which is what makes MSMQ robust to transmission failures.