Just read the comments here for some invaluable advice.
The best advice mentioned there is certainly to call (using Skype?) the US Homeland Security Office: with all their hacking power, it’s most certainly these guys who messed up Skype by trying to eavesdrop on my conversations ;-)
Update: Skype discloses the real cause.
That’s why I don’t rely on Skype…