Helping people with computers... one answer at a time.
Judging by the number of questions I get on MSN Messenger, they're not alone. Do they lose it if the service stops working? I get a rash of panic-stricken questions each time that happens.
The other question I get a lot is "my school's blocked MSN Messenger, how do I work around that?".
I'm not sure that this problem can be solved with technology alone, but there are some things to do...
That solves the immediate problem, and depending on how resourceful the kids are, that might be enough.
But kids can get very resourceful. They might install a different IM client, use a different IM service, or use one of the web based alternatives.
You can try blocking access to certain sites by using the "hosts" file to block access to them. Set their IP address to 127.0.0.1 (a special address that means "this machine", and effectively blocks access to whatever domain you've associated with it). Make sure to set permissions on the hosts file so that the account that the kids sign in with can't modify it.
Sadly, techniques like that are really only piecemeal, and prone to error. As soon as you plug one leak, your kids can find another.
Another approach is to look into some of the firewall or parental spyware packages, which may allow you to block specific applications. Again, while a stronger step, there are ways that these can be circumvented as well, if the kids are savvy and determined enough.
As I said, I'm not sure that this problem can be completely solved with technology alone.