Sharp IR Distance Sensor gives the wrong readings
Seems the issue was power spikes after all. I added a 100uF capacitor across the Vcc and GND connections on the sensor and it solved the issue.

Datasheet recommends 10uF which I tried first but 100uF did the trick.

Thank you very much for your answers