Skype has been plagued over the years with the problem of spam 'contact requests'. It's a way for 'sexy girls' to get around your privacy settings and still contact you. While I have my privacy set to allow contacts only from people in my contact list, there is no way to block contact requests, in in reality I wouldn't want to block contact requests anyway since sometime legitimate people do contact me.
So, several times a day I have to acknowledge, decline, and block requests like this:

The Skype forum indicates they are working on it, with 14+ pages of user complaints
here and
here. Many posters in this forum claim that it's a difficult problem and that users should just disable contact request notifications. I don't think it's a difficult issue, and I also don't want to miss out on legitimate contact requests.
What I don't understand is why this is such a problem for Skype (and Twitter), but not for other services. I don't receive spam friend requests on Facebook, MSN, or Google Talk. There seem to be a simple ways to fix this. Off the top of my head, using social network metrics:
[1] detect new accounts that send contact requests to > N (say, 100) people
[2] if within those N people, the interlinkage ratio is low (e.g. fewer than 2% are connected to one another), flag the account as spam and cancel all those contact requests, block the IP.
This might work because if someone populates their initial contact list for Skype from something like their email database, it's likely that within that email database there are people who are also mutually connected. Whereas a spammer choosing random names or using an alphabetic list will likely request contacts with people who for the large part do not know one another. This would be suspicious.
To augment this, what about some regular expression processing to detect suggestive words in the contact request?
Another option, which LinkedIn uses is to request you to enter an email address of the person you are trying to contact, to confirm that you really know them. I realize Skype intends to facilitate introductions of like-minded people who don't otherwise know one another, but I have never used it for this purpose and I don't intend to. Some sort of captcha/secret question should be an option in the privacy settings so that only requests from people who know me make it through.
I'm not sure how MSN/Google etc. manage these sorts of spam contact/link requests, but they do a good job.