Nagle's wouldn't cause "disappearing into the kernel", which is why disabling it doesn't help you. Nagle's will just buffer data for a little while, but will eventually send it without any prompting from the user.
There is some other culprit.
Edit for the updated question.
You must make sure that the client is receiving all of the sent data, and that it is receiving it quickly. Have each client write to a log or something to verify.
For example, if a client is waiting for the server to accept its 23-byte update, then it might not be receiving the data. That can cause the server's send buffer to fill-up, which would cause degradation and eventual deadlock.
If this is indeed the culprit, the solution would be some asynchronous communication, like Boost's Asio library.