I know... you could write a JNI wrapper DLL around the C++ MS Messenger Service DLL. This would allow a Java program to send messages over MS Messenger. Of course, the remote machine would need to have a Messenger client running to catch such messages.
Google for something like "MS messenger api" for more info about that. Then go look in the "Other Java APIs" forum for more JNI info.
Am I sure this will work? No, but I don't see any major obstacles except the amount of effort.
HOWEVER... I wouldn't blame people if they stopped running MS Messenger because they get too many pop-ups. That's (or at least should be) their perogative.