We run an internal jabber (XMPP protocol) server in house here on Ubuntu, but there's a really good windows version also. Tons of free Jabber clients out there.
Server http://www.igniterealtime.org/projects/openfire/index.jsp
We us Pandion as a client since it's multiplatform: http://pandion.im/
I use XMPP for sending out notification message like that. With the added bonus of now having a corporate chat system.
Openfire runs pretty well and is easy to admin. There is a broadcast plugin that will let you send a message to all users or your can use a client that has that functionality. . http://www.igniterealtime.org/projects/openfire/index.jsp
You can use their Spark Client, or any other client that uses the XMPP protocol (Pidgin etc). I used a heavily branded version of Pandion. http://pandion.im/
I ran openfire for a few years for a call center and it was great. We had issues with the collectors chatting all the time with each other when we used aim, but with this we were able to cut them off from talking to each other and just let them talk to their managers. I highly recommend trying this.
I use IKVM with OpenFire. I'll see how this version works out and blog my results.
EDIT: http://unquietwiki.blogspot.com/2011/03/compiling-openfire-xmpp-chat-server.html