It seems to be a documented bug...

Warning
Registry Edit: Do not use unless you've backed up your registry
To delete the exception, delete all Skype entries here:
"HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\ Parameters\FirewallPolicy\FirewallRules"
Personally, I recommend switching to a third party firewall, I don't trust the Windows one, how am I to know that Windows isn't magically downloading updates to whatever. This would work along the lines of the recent self-updating WAT update.
Comodo Firewall is one of the best free options out there.
Zone Alarm isn't bad either.
If you have a good anti-virus and want to get the full internet security package that isn't bad idea either, just don't use Comodo's anti-virus. ESET isn't bad, Avast is good, Avira isn't bad, MSE is good but as I said, no Windows Firewall. AVG is junk now and a memory hog.