Can OS X apps access my contacts even if I don't give them permission?
As this was an upgrade install, you had used Skype already for quite a while, right? I assume that Skype is simply displaying its own database which it build-up before Mountain Lion.

I myself don't use Skype, so I just installed it and used my firewall to monitor what files Skype accesses:



During the setup I was also prompted by Mountain Lion if I wanted to grant access to my contacts. I denied access. If I had granted access to my Contacts, the firewall would have intercepted as a second barrier (I've set it up this way). But this was not necessary.

After several restarts Skype had written to ~/Library/Address Book Plug-Ins/, but your contacts are stored in ~/Library/Application Support/AddressBook. As you see in the first picture, Skype never gained access to my contacts.

And indeed, there are no entries in Skype's own address book:



So what you have probably achieved now in Mountain Lion is that Skype will not gain access to any new Contacts that you add to your address book. When Skype had access to your contacts in Lion, it copied them already and there's nothing you can do to undo that.