Even though Everyone has access to the queues, and that sounds like there's nothing in the way of communicating freely, I'm not sure that it works that way.
In any case, I suggest you make sure your IIS app pool is runnig with some dedicated service user identity, which you can also use as the user account under which your server process is running.
With MSMQ, messages are never lost - so in your case, the subscription message is most likely sitting in an outgoing queue on the web server machine, or it might have been moved to the "Transactional dead-letter queue" which is where MSMQ ends up moving stuff that it cannot find a place for.
Could you try and take a look at the outgoing MSMQ queues and/or the transactional dead-letter queue to see if it's a user rights problem that is haunting you?