NavAgent taking insane paths when going over Network

Ok, so I'm making a multiplayer game where I need to send my soldiers from one point to another. Doing it in "single player" on the map, using the standard NavAgent component results in smoothly running unit, from one castle to another, reaching its destination without any issues. However, when I try to do it over the network, when 2 players are connected things start to get weird. The soldier is instanitiated via Network and then I set the target position, to which it should move. That's where the "magic" starts - the soldier takes the turn too late, falls into the trees and bounces off them (he can't walk through them), then he can't aim into the exact point I told him to go to, but keeps walking around it, making turn after turn. The whole movement gives an impression like he's too fast and too heavy - he goes straight for some time, then he cant turn in the right moment and it looks like some centrifugal force won't let him move the way I want him to. But it can't be really physics' problem, since without networking, he moves perfecty fine, and navagent steers him just fine. What is the problem then?! Is NavAgent having some trouble locating the little fella and giving him proper path over the network?
I tried looking up some similar problems on the internet, but couldn't find any sensible solution.