It seems you are using a recast graph.
Navmesh based graphs have the unfortunate problem that when pathfinding using triangle centers, it might not always find the optimal path. Grid graphs are better in this respect. This is mentioned here: http://www.arongranberg.com/astar/docs/getstarted2.php#navmeshnotes
You can combat this partially by using a tile recast graph to break up the very large triangles.
If you use the RichAI movement script, that will try to simplify the path a bit more to detect when a suboptimal path has been taken. That is not free however, so that might be a bad idea considering you have quite a lot of units.
To make units take slightly different paths you can try the AlternativePath modifier. It is intended to be used with Grid Graphs, but I think it might work in your case as well.