I confirmed, and verified, all 256 values of the 8-bit output the hardway (using a data logger through a complete rotation). The first 10 values are as listed. If you search this sequence on the internet it crops up in the odd gray-code-related conversation, but no where does anyone say what the algorithm is.
My first suspicion was that I'd connected the sensor up the wrong way, but the colours are correct as defined by the data sheet and, further, a detailed Excel analysis of this sequence to a standard gray code sequence (eg 0, 1, 3, 2 etc) shows that it's not possible to make them the same just by swapping the bits around to undo a possible misconnection.
I fell a little bit more confident that I'm not being a dufus as one of my colleagues used the same rotary encoder in one of his projects and ended up creating a truth table by hand because he couldn't work it out either - and he is a good electronic engineer.
So the mystery continues......
What get's me is that the Omron data sheet doesn't mention it at all - pretty crappy for a $250 sensor!