There are quite a few things that can cause desyncs in a game. Normally it has to do with your triggers.
Certain triggers may cause desyncs in your map. Perhaps in some games, you don't do certain things so these faulty triggers never fire. Sometimes these triggers may only cause errors under certain circumstances which varies each time you play. Each time you play, you do things, chance does things, your AI does things and the other players do things in a million different ways. That's why it only sometimes happens.
I'd try disabling 1 trigger which is likely to cause desyncs one at a time and test your map. Since it happens only sometimes, I'd test it a couple of times for each trigger. Once the desyncs go, you know which trigger you disabled last (which was causing the problem). This process is tedious and takes a while, but it seems to be the only way (given you have no obvious coding mistakes such as improperly used locals).