You were right.
I did not have a scope but it was on my shopping list for a long time so I actually just bought a brand new Siglent SDS1104X-E for this (yay me!). I was appalled by the level of the encoder line signals. First, while being fed a beautiful +5V from the Roboclaw, they only output a peak-to-peak signal of less than 3V with a noise level of at least 1V, sometimes even much worse. Awful
I did disassemble the robot encoder and could see that snubber cap right across the power lines of the motor but it would be quite difficult to unsolder without removing the magnet and that one seems to be press fit on the axis so I was unsure if I would be able to put it back.
So I settled with adding a capacitor across the A-B channels of the encoder and the GND at that did the trick! The count is now fine again with both Motion Studio and my Arduino. 0.1uF was too high (the signal was too slow to raise and was chopped off at high speed) but the magic value seemed to be a tenth of that (10nF). You can see below the dramatic improvement of the signal:
The lower plot is with the cap, the upper one is the other channel without any cap (raw signal). Zooming in I could actually see that the noise is made from a series of spikes at 20kHz. I guess that's the PWM frequency of the Roboclaw.
Thanks a lot for the help!