Tried already with attachInterrupts.
Still skips codes...

Please note. Skipping of codes does not happen if I rotate very slowly.
Again, I'm not familiar with the encoder or pulses you are receiving or, how you set up the interrupts. Did you set the interrupt as a positive flank detection instead of pin change? That's quite an important part.
Are you running the serial port? I don't have the serial port library with me but, my guess is that when you send data through it, you disable interrupts while you're sending data and then enable them when the transmission if finished. At higher speeds, this causes a problem in your software.
Do this, delete all the Serial.print*() functions from the software. Create a condition that you'll only send data if a request from the serial port is received. Say, every time you send a "T" over the serial protocol, the program sends the count to you. Run the encoder fast for a set number of times, stop, and check the count on the encoder input.
This will tell you if the problem is on the serial port or not.
However, the best way to do this task is to free the system from processing just to count.
Check how to set up Timer 1 as a counter, and then place the encoder signal in that input. It won't detect direction, but it will count. probably fast enough for you to catch it.
I'm at work now, but if you can't find it by then, I'll post an example for you to see what I'm talking about.