Ok, first of all there is no such thing as identical anything. Each motor will have it's own set of torque and friction and inductance characteristics. Further, whatever you are driving on each side will also differ in terms of the load applied to the motor. Further still, with open loop systems, two motors can actually interfere with each other mechanically.
You could try switching motors from either side and see if the problem follows the motor, i.e. it stays on the same side. If it's the latter then I would be investigating what is different about the loads on that side.
However, in general, driving stepper motors without commutational feedback is actually a rather unreliable thing to attempt especially at any considerable speed. The phase angle at which you step the motors is crucial to dictating whether your motor will accelerate, run, or just stall. This is problematic is a fixed load scenario, and is critical in a variable load application.. like a robot.
The image above shows you how the shaft torque varies depending on it's position relative to the selected phase coil. As you can see the torque is sinusoidal and zero when the shaft and selected coil are aligned. When driving a stepper motor you want to maintain the torque somewhere in the peak section. For maximum acceleration you want to switch phases when the shaft reaches half a step away from the selected phase position. At that point, then next phase will be 1.5 steps away and the torque will grow on the other side of the peak.
If you switch phases too early you will actually apply negative torque which of course slows the motor and everything gets out of phase, the torque becomes directionally random, and the shaft will stall and just sit there screaming at you.
In order to get steppers to work reliably, you either use a phase stepping time profile which is calculated based on the measured acceleration profile of the system, or you use positional feedback generated by an encoder which has the same, or multiple, pulses per rev as the stepper motor has steps.
The acceleration profile method tends to be more problematic since you have to figure out a profile for the best AND worst case loads and those loads need to be relatively constant. Often best and worst case are so different that a common step profile is impossible to obtain. The encoder method is much more reliable but does of course add extra complexity and cost to the system.
Encoders can vary in cost depending on your requirements, especially if they need to be hermetically sealed. If your stepper motors are low steps per revolution, a do it your-self "slotted" wheel and optical, or magnetic interrupter is also an option.
Your are describing a robot application which will, presumably, have high load variability. As such, you really need rotary encoders on each motor adjusted to give you the best phase angles and torque so you can control each motor appropriately.
If you ARE using phase angle feedback already and it's still stalling, either you have a software or feedback issue, or the load is simply too much for the motor. It is unlikely to be a driver issue.
ADDITION: Since you are using two motors to drive this robot along, even with shaft encoders, you will need some clever control algorithms to keep both motors in synch so the thing drives in a straight line.
This usually entails monitoring the speed of each motor on a step by step basis and "braking" or "idling" one motor while the other one catches up. More complex torque/current control methods are also possible that will provide smoother operation at the cost of slower response time. Which is best for your particular application is of course at your discretion.
It is normal to also include acceleration and deceleration profiles as an upper control layer here too. The encoder feedback system gives you the maximum acceleration and deceleration possible with the load setup, you then use the profiles to modulate those forces to de-rate the acceleration curves into a controlled subset. That way you can accurately stop your robot at a required step position.
