After a long while trying to work out what was going wrong with another customer's system, I finally cracked it. There were two servers and we could send messages between them in one direction but not the other. Messages would happily go into the outgoing queue and then disappear.
The first place I looked was in the IIS logs on the receiving machine - the web service is the first place that the message will reach so we need to check if the POST request is getting through.
2006-10-05 12:55:49 W3SVC1 THESERVER 10.6.0.10 POST /msmq/private$/queuename - 80 - 10.6.0.1 HTTP/1.1 - - - 10.6.0.10 404 0 64 0 3292 0
Sure enough, the message was coming in but the webservice was responding "404" - basically the path to the MSMQ queue could not be found. The configuration looked OK though - the MSMQ virtual directory showed up in IIS Manager and the private queue could be seen in Computer Management.
Next troubleshooting was the MSMQ logs on the receiving machine - maybe there was an error when the web server tried to talk to MSMQ via the Message Queuing ISAPI extension (Mqise.dll). I spent ages collecting and examining the logs but all I could see was successful message traffic arriving in the queue. It was only when I remembered that the server was used for non-HTTP messages as well that I realised that I was looked at traffic totally unrelated to the problem - it wasn't even being logged by the ISAPI extension! In fact there was NO logging for the extension at all so I could tell that the POST requests never got as far as MQISE.DLL.
So maybe there was something stopping the POST requests coming in. Looking at the properties of the MSMQ application...
and clicking the Configuration button...
I noticed that a 3rd party product was higher up the order of implementation for the Wildcard application maps. The idea is that all the application maps get processed in order - once one extension has had its chance to process the incoming request, it should pass on control to the next extension. In the customer's case this never happened so the Message Queuing ISAPI extension was never executed which explained the lack of MQISE entries in the log files. Once the customer had moved MQISE.DLL to the top of the list, MSMQ messages over HTTP arrived immediately.