One of the basic principles of MSMQ's design is that sender and receiver are decoupled. The sending application does not need to know whether the receiving application is running or even reachable under current network conditions: it can just send, and let MSMQ take care of getting the message to the destination at whatever time that's possible. (Note that the decoupling occurs within MSMQ, and that both of the applications are tightly coupled to MSMQ, requiring the local MSMQ service to be running in order to perform MSMQ operations.) This design principle determines how MSMQ behaves in various circumstances when a queue doesn't exist.
When sending, the local MSMQ service knows what local queues exist, so it immediately returns MQ_ERROR_QUEUE_NOT_FOUND, hexadecimal value C00E0003, if you attempt to open a nonexistent queue for send. However, opening a remote queue for send will always succeed, regardless of whether the queue or even the machine exists. This is where and how the decoupling between sender and receiver occurs — MSMQ has no way to tell the difference between a remote machine which is temporarily unreachable, one which used to exist but is never coming back, and one which just plain doesn't exist, so it makes no attempt to do so. It just allows all sends and goes through the same retry procedures to attempt to get the messages to where the sending application said they should go.
Receiving is a little different. If you open a queue for receive and the queue doesn't exist, you will always get error code MQ_ERROR_QUEUE_NOT_FOUND back regardless of whether the queue is local or remote. If the queue you're trying to open is local, then the MSMQ service knows whether the queue exists; if it's remote, then the local MSMQ service must contact the MSMQ service on the remote machine. As described above, decoupling occurs on the sending side, and the original designers chose not to include a second point of decoupling on the receiving side, so even remote receives are tightly coupled.
Getting back to the title of this post — in summary, there is only one place where this question can occur: when sending to a remote queue. In all other situations, the presence or absence of the queue is immediately obvious in the return code of the API call. When sending to a remote queue, this is a question that you probably shouldn't be asking, to be honest. If your application determines whether a remote queue exists before sending to it, then you have given up the decoupling which is a major reason to be using MSMQ in the first place. In part 2, I will cover timeouts, acknowledgements, and dead lettering, at least some of which you should probably be using anyway, since they not only handle the case where the remote queue doesn't exist, they also handle all the other things which could go wrong even if it does. And if you really do need to know whether a remote queue exists, I'll cover how to find out in part 3.