Do you just have 1 ACL line that says deny ip any any, or you have other access-list that might have permitted the skype or messengers traffic?
If there is existing skype or messengers traffic, it will not be blocked when you just apply the deny ip any any until you clear the connection.
"clear xlate" will clear all existing translation and connections. Please try to see if skype and messenger still work after clearing the xlate.