Well if you look at my post on
this thread I have a suggested encoder. Provided you've been using good ISR code practices, this should work at an absolute maximum freqency of 12.5KHz for two channels (aka 3,000RPM) but will not quadrature decode properly at this speed. You'll have to find out what your specific code can handle, unfortunately I can't tell you exaclty how it will perform on your code.
Although, I have no idea what you're mounting this to. Custom transmission? Something AndyMark? Bane Bots?
If you have any other/further questions, post.
-q