It depends a bit on your target audience, but my experience ( more in small/medium scale development than very large scale work ) is that detailed design documents are arduous and boring to write, rarely read and tend to end up out of date by the time a project is delivered.
This does not mean that they are worthless - if you are delivering something for someone, there needs to be an authoritative and agreed statement of what will be delivered sufficiently detailed that everyone can point to it in case anyone is dissatisfied with the deal and say "this is what we promised" and evaluate it against what was delivered.
If I were setting up a company to build a product, however, I wouldn't worry so much about a detailed specification. I would want to document what we were going to do, but I wouldn't want to go into too much depth regarding how - that is the part that is most likely to change and leave the documents out of date and useless or even inaccurate enough to be actually obstructive. I would prefer to document the "how" stuff in code using whatever documentation format the language or IDE supports best, so that as the code changes it is easier to update the documentation at the same time. It won't stop it going out of date, but it will reduce it somewhat.
Ideally you would want a design document that could double as your manual when your code is complete, but I don't know of anyone who has managed that successfully.
I am the author of pg_message_queue which is a very light-weight channel/queue system in PostgreSQL designed to facilitate database-level integration. Messages can then be forwarded to a heavier message queue, or the like, or they can just be processed. The use case is for things like "I want to send an email from the database" and helps solve the problem for PostgreSQL without really awkward transactional processing problems that could result.
Our documentation is at http://pgxn.org/dist/pg_message_queue/
I won't say it is the best documentation out there but it is sufficient for our use case. Compare to http://www.rabbitmq.com/documentation.html which is the rabbitmq documentation and you will see how different the requirements of the documentation in fact are.
But like all docs, keep your audience and use case in mind, and go through it conceptually and programmatically.
Edit Ok I see what I misunderstood. I would suggest starting at least with an outline of technical documentation. If you have it from someone else, great. If not, at least come up with an outline of what a technical programmer's manual should cover.
It sounds to me like you are looking at documenting a network protocol rather than an API. Sorry, I did read it and I missed that part. It's still not clear to me if this is direct over TCP, or over HTTP, or something else. To the extent you are reusing other protocols, the work is easier.
Either way, I would divide up the documentation into three sections. The first would cover message structure generally. This would include headers, message body specifications, etc. but would be at a general enough level to provide a reference for section 2.
Section 2 would cover the specifics for each message type. Again it depends on what exactly you are re-using how much depth you need to go into.
Section 3 would provide examples for how the communication would work using sets of mocked up messages.
Best Answer
Do you have appropriate testing (including, but not only, unit tests) for the system? It seems like you don't, in which case I would start by adding enough tests to be sure that the application behaves as expected (since it fails to fulfill the requirements for the moment, if I understand well your question).
Then, documentation's purpose is to introduce the code to the new developer who doesn't know anything about the architecture of the existent codebase. It means that documentation is not really intended to find where a problem occurred.
When the piece of code behaves unexpectedly, you often start reading code, not the actual documentation, which can be obsolete, or just totally wrong or misleading. In practice, when systems I debugged had documentation, it was obsolete or wrong all the time (concerning the debugged point). No exceptions. Either the documentation was written from requirements and the error was introduced in the code, without reflecting the documentation, or the error was the consequence of slight changes at code level, while documentation stayed the same.
Following the comments, I see that I slightly misunderstood your question, which is more about "How I understand the existent codebase which has no documentation at all". It depends. In my case for example, generating class diagrams is something precious. This is the first thing I do before starting to work on someone else's code, and sometimes the only thing. But I also know people who don't bother generating those diagrams, because they find it totally unhelpful.