The output bit pattern is supposed to be a Gray code, therefore under no circumstances should two outputs be changing simultaneously...

Not according to the sheet which shows typical quadrature?
The change occurs midway between indent, so it appears to be geared to very slow rotation rates.
OP: What is your application?
Max.

 

Max,
My application is very basic human interface (similar to volume control).
Pradeep

 

Then I would suggest to take a sample output while turning slowly manually and monitor output with a meter.
If necessary chart output via a simple 360° protractor on the shaft.
The transition should occur midway between indents.
Max.

 

Not according to the sheet which shows typical quadrature?
The change occurs midway between indent, so it appears to be geared to very slow rotation rates.

Max: by definition, Quadrature is a Gray Code...

 

I haven't worked with gray code at all, except marginally, I work extensively with quadrature encoders though.
Max.