Andy Abramson reports in his VoIP Watch blog about trying out the iSkoot client for Skype on the new Android G1. One of his comments in particular caught my eye...
"3) Presence isn't working right. I never saw my entire Skype buddy list as the presence information seems to not be real time. As a matter of fact, sometimes you don't see your buddies on line that you may be chatting with on a Mac or PC using the real Skype client."
I have seen exactly this problem on Skype for Windows and Linux, and I have had exactly the same experience that he reports - I have been chatting with someone via Gizmo5, ooVoo or SightSpeed, and at the same time Skype reports them as not being online. It is ridiculous, frustrating, and extremely irritating - when Skype says a contact is offline you can't call them, or even send a text message. This problem has been reported in the Skype Jira bug-reporting system for well over a year, and there have been hundreds of complaints in the Skype Community (User Forums) about it, and it obviously has still not been fixed.
My personal opinion is that the real problem with this lies in the Skype "SuperNode" system, it may well be that it is not up to handling the number of users they have now. It would be ironic if the massive number of duplicate/dead/abandoned/spammer/pornographer accounts that Skype loves to brag about in their "338 million registered users" marketing rubbish were actually causing this kind of problem for however many "real" users they have... but that is pure speculation on my part.