well, the usual way would be to setup firewall rules (read : iptables rules) to drop some request from your "clients". It is actually what you RH done to NAT, mean, to write some iptables rules.
All you have to do is to add some rules to "drop" ips _before_ the nat rules.
Blocking messenger is more complex. You have to find the correct port number to block (as example, MSN uses 1863) , but these days most messenger uses port 80 (which is also HTTP, making it really hard to block). You could also block the messenger's server hostname, but it would hard to find out and I doubt it will work that great.