The Free Software Magazine has a great how-to for building an IM server. The author built a low-cost instant messaging solution for one of his kid's school. IM is so popular that it is difficult to block, but building your own server avoids many of the problems with a public service.
The only real problem is with support. The good news is that the system he created is probably near indestructible.