Kostya,
You might be thinking about this scenario already (I am judging from your questions), - but just in case: Is it possible that the hidden message is close to the "boundary" of how many messages are synced (or kept). Then, it goes "beyond" that boundary. But when some messages are deleted, it comes back into the set of messages synced. And that somehow leads to the message showing up as not hidden.