Hey JasonS,
One possible approach might be to separate the problem of path finding from the problem of overlap prevention.
Instead of having the Soldier be the object doing the path finding, make your current path finding object invisible, and make a new soldier object to follow the path finding object. Then give that Follower object the physics behavior, with a constant force pulling it towards its personal Pathfinder. By default, Physics objects won't overlap each other, and will instead slide past each other, or bunch up like gumballs in a jar.
But what if there's a physics traffic jam, and one of the physics Followers can't keep up with its Pathfinder object? After all, if a Pathfinder goes around a corner while the Follower is stuck, even if the Follower later gets un-stuck the Follower may not be able to reach the Pathfinder by moving straight at it, via a physics force. We need to make sure a Follower never gets left behind.
Basically each Pathfinder should be a mini Dr. Alan Grant. :)
To prevent Followers from getting left behind, you can pause the Pathfinder if it gets too far from the Follower. "Too far" in this case might mean 1 or 2 soldier widths. Ideally the soldier (Follower) will nearly always be just behind, and almost touching its Pathfinder.