I2C - communication mulfunctioning on Arduino Mega 2560

Is it possible that you left the address pins of the connected devices floating? That would almost explain the range of addresses the scan found.
I support the suggestion of WebMaka to start with an empty bus and add one device after the other.