Servo motor's are pretty simple, as long as the encoder isn't flakey I'd be surprised your problems are coming from the motor, more likely its the servo drive and/or PC interface. If the encoders are flakey they can probably be replaced.
You may be able to keep your current servos and switch to Gecko servo drives and a breakout board like the ones from
http://campbelldesigns.net/ or one of the serveral other breakout card vendors. I use a Campbell board and its worked well for me.
For the speeds you described steppers would work also, but it would be more expensive that way, and more work also to replace the motors. You'd also have to make sure your current supply voltage will work with the steppers you chose.
Paul T.