Windows messenger has specific ports and servers (but if you use file transfer or voice service it will uses p2p connections).
I think it is the same with yahoo.
For skype try to use L7 filter or, if your custumers use specific devices like skype-phone in their lan, mark traffic from src-address.