I was complaining that Skype ate my contacts list a few days ago (both on the Mac desktop and the WinXP laptop). One of their PR folks contacted me and hooked me up with support and they responded:
It appears that due to a temporary error your contacts effectively disappeared from one of our databases. We have now restored all of them and you should be able to verify this by simply logging into your account.
Thank you thank you thank you!