I may add fourth: The approach I tried succeeded despite all terror Erik was spreading that I'm bound to fail :)

You can say it's a hybrid between 2 and 3.
The "fast part" done by custom electronics (in my case it was on 74LS series gates, but if you can make CPLD, go for it, you'll save DAYS of soldering :) and the "slow part" in software. In the electronics generate (for typical 12MHZ clock) some 5us long low pulse on ANY transition, using retriggerable monostable multivibrators. They swallow all high frequency noise (generating one pulse on every "noise event") and normally generate 4 falling edge interrupts on 1 quadrature. Perform sanity check: A, B - current, A', B' - previous. Place A,B, A', B' all in ACC making sure other bits are zero and check P (parity of ACC) - all legal transitions have odd number of bits set; if the transition was illegal, just disregard it (RETI) - you don't lose a count because the count didn't really happen, it was a mistake - the noise just occured.

Then take A XOR B' as direction and count the turn. Store A and B as A', B' for use in next count. That's about it.

I successfuly counted about 3RPM from a 1700CPR encoder giving 7200 impulses per revolution and performing several other tasks on a normal speed '52 clone.

If you need higher speeds, go for all-in-hardware solutions. Here the tricky part is selecting the timing of the multivibrators: The pulse should be shorter than shortest expected period between legal transitions (so you don't miss counts on relatively fast rotation) and long enough to connect all line noise into one "low" area generating only 1 false (and detectable as such) interrupt instead of keeping the program locked in interrupt calls indefinitely.