Don't think of it as parallel processing. Think of it as ordered processing. When order matters, you think of it as ordered processing yet implement it so that it has the quirks and efficiency of parallel processing. There will have to be some thread control for ordered processing. Each connection object should have a static variable isBusySendingMessage or something. A boolean per packet in which order matters.
EDIT1:
Do you "pipeline" the messages such that while one message is being sent, another is being converted into a packet? (No time to look at the code.)
EDIT2:
Sorry if this post was unhelpful. I don't have time to look at the code, but thought I may go with the chance that this may help.