A current sensor is probably the best option for preventing stalls. The current sensor reads the current that the motor is drawing. Motors have a rated stall current; if the current sensor reads this current, then power can be cut to the motors for some period of time before allowing the program to "try again".
Another related issue occurs when you want to apply power for the first time. Before power is applied to the motor, the default for a current sensor algorithm will be "OK, you can power the motor", because the current is zero. However, the default for an optical encoder algorithm will be "No, you can't power the motor" because the encoders aren't changing values.
To get around these problems, you need to work harder with encoders than you do with a current sensor. You need to consider both a) is the motor stopped because no power is applied or because it is stalled, and b) is the motor stopped and ready to startup again. Fixing a) is pretty easy by adding in the question of "is power applied?", and only running the stall check if it is.
The much tougher question is how to get the motor running again. What I did was the following. Consider that for the motor to begin again, we want the user to recognize a stall and remove power to the motor. After this point we want the program to be allowed to attempt to run the motor again without implementing the stall check. There should be a "grace period" where the motor gets a shot to start moving again, BUT the grace period can't be too long in case the motor is truly stalled. So first we need an algorithm to recognize if the joystick has been returned to a zero position, indicating recognition of the stall. One such algorithm is as follows. We keep track of the last time the motor power was non-zero... if more than 200 ms have passed since the last non-zero motor power reading, we assume that the joystick is centered and we raise a "stopped flag".
Once that is all in place, we can put it together with the stall check algorithm as follows. If the stopped flag is raised and the joystick is now in a nonzero orientation, we apply power to the motor for 300ms without running a stall check. Once we've done this, the "stopped flag" is lowered and the stall check will be occurring again.
The algorithm does add a level of latency due to the delay which stops the microprocessor while a motor is run. But this was the best I could come up with at this point.