Ou podes comprar um encoder incremental... Mas... mais de 3000 RPM? 
Com um encoder incremental de, por exemplo, 250 pulsos por revolução a 3000 RPM ias ter:
3000 * 250 = 750000 pulsos por minuto.
750000/60 = 12500 pulsos por segundo, ou seja, 12,5 kHz.
Se apenas precisares de ver a velocidade e não o sentido e distância percorrida, podes ligar a saída do encoder a um timer e medir o número de pulsos por segundo, ou 100, ms. Isso dá-te a velocidade.
O que tens de ter em atenção é que o Arduino pode não ser capaz de ver isso tudo facilmente. Provavelmente, e sem prestar muito tempo a pensar nisso, terás de ter algum cuidado na programação disso.
Qual é o estado normal desse motor? Ou qual é a gama crítica onde pretendes ter a melhor resolução do encoder?