No heat and temperature gauge going up and down

Again: if the p0134 code comes up again it doesn’t automatically mean it’s the O2 sensor.
It only means the signal from the sensor isn’t ‘normal’.

Any shop that double checks things in order to verify things and possibly save you needless repair costs sounds legit to me and is a shop you should use when needed.