Actually i agree with imcintyre.
When you block skype there'll be something else. You should take harsher measures and they would stop. They'll just start using ICQ, Yahoo, web messenger (you can access MSN from the internet),...
But you CAN implement a password for accessing internet, blocking websites, internet content and tracking their browsing habits (search for squidguard).