Of course it's possible. The Internet is simply a network, and all the
traffic on it is messages from one computer to another. Email (SMTP) and
Windows Messenger are 2 of  thousands of types of messages being transmitted
constantly from one machine to another, most of which you never even see.

What you have to do is to create a client/server networking application,
which has both a network client and a network server component. The server
listens for and responds to incoming connections from other clients, and the
client talks to a remote server. If you think of it like a telephone, a
telephone has a mouthpiece to talk, and an earpiece to listen. But in order
to talk to someone on the telephone, both people need to have a telephone
with both a mouthpiece and a receiver, and the ability to call up the other
person's telephone.

An easy way would just be to have a sql database (either online or on the
local network server) that puts messages in a table with a "from" userid,
"to" userid  and the message itself, maybe with some priority and a "read
status" flag.