Navmesh agent returns path with corners in wrong order

I am using a navmesh with agents to calculate paths in fairly large map. I am not using the agent’s movement, just SetDestination and then just getting the path’s info to move the entities myself.

It seemed to work just fine but lately I started to notice that some agents were moving backwards when they had a clear path ahead of them.

Here is an example of this, with colored spheres to mark the position of the nodes: Node 0 is the agent’s current position and Node 3 the destination. It should go straight towards the destination, but instead it adds another node behind the starting position.

What could be causing this?

Here are the settings for the navmesh. It is a pretty large one as the map is big and open and I am trying to avoid dividing it into several smaller navmeshes. I tried adjusting the voxel size and the tile radius to increase the resolution of the navmesh, but I keep getting the same issues.