How to minimize the impact of erroneous sensor readings?
I have quite some experience in Lego Mindstorms and I can tell you that their ultrasonic sensor is extremely inaccurate as you described - from what I read online, the ultrasonic rays travel in a V shaped path instead of in a straight line (it causes readings not to be linear with distance). Detecting an object with a round surface makes it worse, because the ultrasonic rays end up scattering all over the place.

What we (my team and I did) tried to do was to cover up half of each of the sensor's emitting and receiving outlet hole so as to force the ultrasonic rays to travel in straight lines. We also tried taking averages, root mean squares, differentials, integrals and what not of samples instead - but both did little to solve the problem, especially when sensing across distances that are far away (> 100 cm). 

We ended up switching to one of Mindsensors' laser based distance sensors.