The MSMQ documentation states that a send is "always an asynchronous operation". It's been a while since I've worked with MSMQ, but IIRC as soon as you send, the message is flushed to disk locally before it even attempts to send over the network.
So, while it's not truly asynchronous (it has to wait for the disk write), it should be fairly fast.