After much frustration and wasted time I have discovered an issue with Skype running on Windows XP.
Windows XP puts a limit on the half opened outgoing connections allowed at one time. When this limit has been reached (10) all outgoing connections are blocked. Why? Well it seems at the time, Microsoft thought this would be an effective way to control worms / viruses from having lots of outgoing connections?!? The problem is, as soon as outgoing connections start getting blocked, a lot of software applications start to worry. The issue we were having was with a Postgres database server. The PC could not even connect to a database engine running on itself, due to the fact that the client was attempting to establish an outgoing connection.
Is there a way to check how many half opened connections you have? Sure! Open the Command Prompt, type in 'netstat -no' and check for connections marked SYN_SENT
If you're running Skype on your PC and you have a lot of contacts, I'm certain you'll find a lot of SYN_SENT connections. Skype is a peer-to-peer software application, which means when you're running Skype you're not only connecting to a server, you are also connecting to other users PCs. In effect, Skype kills itself. If you are running Windows XP and have an issue with messages not sending (or coming through) on Skype, most probably you've maxed out your half open connections.