If I repeatedly run "Import Contacts" there are slight differences in the contacts returned. Running against my Outlook address book of ~900 contacts there were 2~3 Skype user contacts different between runs (some appeared between runs and some disappeared). The Skype users were very unlikely to have been actively updating their details on Skype at the time.

I suspect this is actually an issue with "Search for Skype users" because I noticed similar behaviour with that a long time ago.