TCP is stream-based, which means you send bytes without them necessarily being in a "message", so the receiver may get half a message or one and two thirds of messages.
So in something like a game where each message is fixed-size, if I receive a portion of a message I could just keep it in a buffer until I receive the other part. This is a bit tedious, but is there any other message-based reliable protocol? There probably are, but none are implemented in the OS as with TCP and UDP, so I'll have to use some library, which is fine as long as it's easy to use.
I could always make a somewhat-reliable UDP protocol. Which do you suggest?
If you are looking transport layer protocol, then check SCTP. SCTP is message-oriented like UDP and ensures reliable, in-sequence transport of messages with congestion control like TCP.
SCTP is not yet widely used. So I suggest to use TCP with some kind of message framing.
Protocol Buffers, is less known that XMPP but may be of some interest in your case.
http://code.google.com/intl/en-US/apis/protocolbuffers/docs/overview.html
You could implement your own ACK-based protocol over UDP. Prepend the message with a message/sequence number on the sending side and echo that number back to the sender on the receiving side. Start a timer on the sending side for each message and cancel it when you get the corresponding ACK back. If the timer pops, re-send the message.
XMPP is way, way too heavy for this application.
You could use ØMQ (ZeroMQ) as your messaging infrastructure. ZeroMQ provides reliable message passing on top of TCP and other transport mechanisms. It has a C API and a comprehensive guide.
Note that you would have to use an external library for all peers, but you said that is OK with you.
You can take a look at XMPP. It's a TCP/IP based protocol based on XML-messages.