Several things on my search of encoders that would fit my project...
Questions:
Does anyone know where to find datasheets or some info on encoders marked as QEDS-5956#11 and Q9864 (9935)? (question asked after some 2-3 hours over google and such)

Conclusions:
1) If you're not afraid of spending quite some time with oscilloscope on detecting what output is what, there are some high resolution encoders to be retrieved from old printers. (that's that Q9864 part). I got two from a broken HP710C printer. One linear, one rotary, but these are "split" i.e. I can print a new code wheel for the linear and have it as a rotary too. I don't know what resolution they are, but it's very hard to make out stripes on the code bar and wheel - the rotary is at least 100CPR. One worry though - 4 connectors may mean 1 channel - no quadrature, 1 direction. Just my guess though.

2) Option for achieving high resolution from a low CPR encoder... I spent some "quality time" with oscilloscope last friday over encoders from 2 mice and found something very interesting - Analog encoders, that generate sinusoid-like quadratures. So if you're not critical about readout speed (or have very fast ADC), just pick analogue values from the encoder output and match it against lookup table and you have position within one quadrature cycle, with decent precision. Besides, passing this kind of signal through a Schmidt trigger has no way of creating the noise Erik talks about - the signal is a very smooth curve and there are no "edges". It is a bit of a programmer's challenge to make proper use of analog quadrature though.

3) A puzzle. The second mouse contained an encoder that really puzzled me, because the receiver part had standard 3 pins, but... they weren't +5V, Channel A, Channel B. They were +5V, GND and ???. How on earth did it send two kinds of signals for two directions over a single line? Analog 2-levels? Serial byte send? Unfortunately uncautious twitch of hand on the power supply drew smoke from the encoder before I got to solve the puzzle through the oscilloscope.