Unless I'm missing something, this only occurs if someone sends two messages to someone and the receiving user responds to the first message but gets the second message before sending his.

Using average read/write times for a message - taking its length into account - it should be fairly easy to check if someone could have read and written a response to a message. Assuming it is a response if he could have written one in time should be fairly accurate.

You could probably even cheat and use a constant time while still getting good results.