Rotary Encoder to measure velocity

On the electrical side:

The encoder is an old Leine & Linde AB, with 500 ppr, and runs on 24V (I have used voltage regulators to get an input on 5V).

Using voltage regulators for signal voltage translation is not the proper method and is bound to cause problems. You should rather use resistor voltage divider networks or purpose designed voltage translation ICs. Perhaps a schematic drawing of what you have and a link to your encoder datasheet would be helpful to get you something that can be made to work.