Can a user send a message to another Linux box connected to a network besides using SSH and wall ? Neither user has any IM account online, and the program should be able to run without an internet connection.
Now here's the tricky part: Can both computers do this without either of them being a server (peer-to-peer)?
I also found this: http://planimo.sourceforge.net/ It does instant messaging over LAN (though it does use a server, but that is easy to set up) through python, so it should be able to run on Slitaz (and other distros) without compiling.
Good find, @Spork. I think as it is so tiny and does not need compiling, it would probably be an easy program for someone to package. Even the dependencies are listed there for them! :-)