Frank Boyne, 5 star MVP, posted a great response to a question on the MSMQ newsgroups which I felt was worth reiterating.
Basically someone wanted to check if a private queue on a remote machine existed before they sent a message to it. The problem was that they couldn't call the MessageQueue.Exists() method without getting InvalidOperationException.
As Frank explained, this method call isn't available for remote computers, as documented in MSDN.
The path syntax is not valid.
An error occurred when accessing a Message Queuing method.
The Exists(String) method is being called on a remote private queue
The application used format name syntax when verifying queue existence.
The interesting part of Frank's response is what to do about it. Basically, checking that a remote queue exists before you send is no guarantee that the destination will still be there when the message arrives. Or, vice versa, someone could create the queue just after you've found it didn't exist.
Frank's alternative approach is to make use of other features that MSMQ provides, such as negative acknowledgements messages with administration queues.
What should happen is that either:
Alternatively you could use negative source journaling and, on failure to deliver, should see the same class of NACK in the corresponding "Dead-letter messages" system queue.
In summary, don't check if the queue exists but instead handle the non-delivery of the message should it turn out that the queue doesn't exist.