for bcastner's post from yesterday, the filename should be gpedit.msc, not gepedit.msc
Somewhere around TT there's a post giving the IP address range that MSN uses, but I can't find it quickly. A way of blocking access to MSN messenger is to ban connections to the IP address range used by the servers at your firewall (which I hope the general public have no access to).
This will work even if they figure out a way of reinstalling the software. You can use the same approach to block other instant messaging software (AOL, Yahoo, ICQ etc).
Failing that, I'd also check the rights on the public user accounts: check that they are guests or ordinary users rather than power users or administrators, so won't be able to install software.
John