There is a similar question, but I tried changing audio settings.
I'm using Ubuntu 9.04 and sometimes when talking to specific person it just doesn't send messages or receive them. It may even show that person as offline for few seconds (even if she/he is not).
That may not depend on the other side, because it happened on Windows and Ubuntu box.
There is a possibility it's not really limited to Skype and it's more of a wider problem, I'm not sure.
I'm pretty sure this is a long-standing bug in multiple successive versions of Skype for Linux. In my case my messages are delivered only when the other party sends messages to me. There used to be a thread about this on the Skype Community Forum, but unfortunately the forum has been discontinued with no archives available.
if this is limited to only one of your many contacts this person may very well suffer from a poor connection.
ask the person if these problems only occur with conversations between yourself and this person.
Skype has a forum with a very helpful community, you might as well post this quiz there.
If you can get this person's IP address (by asking), you can use various tools starting with traceroute to test your connection to that specific node. It's possible that, as you speculate, the problem lies in the connection between your specific sites.
This can be a poor connection of the other person. I also have similar issues if the other person is inside a company LAN. I am not sure if firewalls are the problem or just that Skype takes some time to find the right ports.
I am not sure if you are already calling the other person or just sending text messages. If you are only sending text messages it often helps to call the other person until you hear the ringing.
It seems Skype then tries much harder to find an available port over which it can talk. Once the connection is made (and you hear the ringing) all pending text messages will go through.
At least that is my experience.
