I noticed that sometimes when I make maps with triggers (not even that fancy, but I am using hyper triggers), the replays on the map are often broken (units stop moving, etc.)

What causes this, and how can I prevent it from happening?

If you use waits in your map and don't watch the replay at the same speed as the live game, it will desync because waits won't run slower or faster depending on the game speed, even in replays.

waits are not tied to ingame time. they are tied to real-time. Transmissions use waits.

I've had broken replays even on melee maps(hunters 3v3), so I don't think it's only about waits. watching it on faster speed does have something to do with it, but I'm not sure if it's the only culprit.

1) I've had replays that I watch on higher speed that don't break, so changing speed by itself isn't(always) the issue.
2) I've had replays break even if I watch them on the original speed(fastest), so speed is not the only possible reason for breaking.

3) Issues in (1) and (2) happened in melee maps, so triggers are not the issue.

4) I've had a game with a broken replay on my PC that I then asked another player to host (who was also playing) and his replay was also broken, so if a replay breaks, it breaks for everyone?

I suspect that the issue might be lag-related and/or having players in observer slots.

However, it could be the case that additionally, certain triggers also break the map in certain cases(e.g. waits when replay watched on higher speed).

On a critical note, you should avoid (i.e. NEVER) using waits/transmissions in your maps, since the majority of maps have hyper triggers and waits create wait blocks when use in conjunction with hyper triggers. use death counters to simulate waits instead.