Missing pulses in fast speeds although using interrupts

Sounds like EMI to me, as the motor speed increases it becomes a problem. Do you have any noise suppression on the motor? Are you trying to run the motor off of the arduino board's 5V supply?