When you say it is losing pulses, what exactly is happening that tells you a pulse has been lost?
Would it be possible to accumulate the encoder changes in a circular buffer, then print from that buffer? That might give you an indication of where the problem is.
Also, I have no experience with this encoder. Is there no bounce at all?