And this "borderline" stuff is something I hear, when talking encoders - is there no way out of this
nope.

Visualize the encoder stopping EXACTLY where the line between optical black and clear is. Now visualize how small a movement will be required for the encoder output to change. In other words, when the machine stop at that position (in your case one of 3600) on the encoder you will get some vibrations and they can be extremely high frequency, so the RPM of your machine is TOTALLY irrelevant when calculating the response of your pulse detection design.

Erik