If you are sending messages over HTTP then there is a chance you may be behind a proxy server which prevents you making a direct connection to the destination server.

This is no big deal - Internet-enabled products such as Internet Explorer and MSMQ always check for any proxy settings so they know how to get out onto the Web. Specifically they check:

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Internet Settings\Connections\WinHttpSettings.

If you have MSMQ messages in an outgoing queue that remains in a Waiting to Connect state then you may want to check the proxy settings are correct.

Here for reference are a couple of Knowledgebase articles for different products that discuss resolving the same root cause (bad WinHttpSettings proxy value):

The Systems Management Server 2003 or SMS 2003 Service Pack 1 Advanced Client computer cannot connect to the Management Point
How the Windows Update client determines which proxy server to use to connect to the Windows Update Web site