Paul__B:
I was commenting on the petulant whine in the first three paragraphs, occupying the body of your post which did not contribute usefully to solving your problem and dissuaded me for one from trying to help.
Yeah my wife told me I shouldn't have wasted my energy feeding the troll. Lesson learned - next time I'll consult my wife first 
Are you now ready to jump in and help?
With the help of my friend, who is not an Arduino guy per se, but knows a lot about electronics and robots, I came up with the following circuit (photo attached), that seems to result in correct RPM readings. I used the biggest ceramic capacitor I had on hand (0.1 uF) between tachometer signal and ground, a 2 KOhm resistor between tachometer signal and VCC, and a 10 KOhm series resistor to the Arduino's pin (mode set to INPUT). The circuit my friend suggested (a low-pass RC filter) actually has the capacitor on the other side of the series resistor. But for some reason that arrangement gave too high readings, and the one I ended up with just works.
Basically he thinks that the 25KHz PWM causes noise in the tachometer wire, so whenever the tachometer switches, multiple interrupts happen in a very short time due to this noise. This noise must somehow be filtered out or debounced (a Schmitt trigger was suggested for this earlier).
I wonder if this circuit is good enough, or should something be improved here.
I am also about to try my friend's suggestion - software debouncing. Will post code if it works.
