Assuming the garage is competent and there genuinely aren't any fault codes logged, it does sound like an internal fault with the odo. Very unusual though for these issues not to trigger code 42 (speed sensor error). Here's why:
The speed sensor's on the gearbox. The signal from it goes to the speedo cluster. The cluster uses it to, well, show the speed. The speedo cluster then outputs the signal to the odo. The odo uses it to count up the display, buffers it, and re-outputs the signal to the ECU.
If the ECU doesn't see a speed signal once the engine's up to temperature and the car's travelling at at least 50mph (I think it uses the other speed sensor to tell what the speed is. Sounds like a circular argument, the details of which I don't know about!), then the ECU logs a code 42 error.
The point is, the gearbox speed sensor, speedo cluster, odo and finally the ECU are in a daisy chain. If you break the chain anywhere, the ECU won't see the signal and will log the error.
Common failure points:
1) Failure of an aftermarket speedo converter spliced into the daisy chain somewhere
2) Failure of the odo's buffer circuit, meaning it doesn't re-output the signal to the ECU
I think you've got one of the following scenarios:
1) your car hasn't been above 50mph when warm since you last reset the ECU/removed the battery. This means that the ECU won't have met all the conditions to log the expected error. Your odo problem is probably (and it is just an educated guess) caused by a faulty odo unit.
2) your car has been above 50mph when warm, and still hasn't logged any errors. This means each component in the daisy chain is doing its job of receiving the signal and re-outputting it, but that the numbers just aren't counting up.
Both 1 and 2 suggest a new odo is required, not a new speedo cluster.