That is why I suggested stalling the motor at a much lower voltage; in general, that is easier on both your power supply and your motor.
It sounds like you do have the right motor, so I suspect that the problem is in how you are reading the encoder. If you post your code, I could see if I can spot an issues with it. Do you have access to an oscilloscope you could use to look at the encoder outputs?
Another method you could try to estimate the speed of the gearbox output is to hold the output shaft lightly against a table and try to count the taps per second. If the motor is spinning at 500RPM, there should be about 8 taps per second, and if the motor is spinning at 1000RPM, there should be about 16 taps per second. Supplying the motor with a lower voltage might be helpful for this too, since at 3V the motor should spin at about half the rated speed, so there will be half as many taps to count.