Have had a similar thing with my desktop monitor, had it for 5 years but a year or so ago its native resolution of 1440x900 would suddenly change so that it was in fact a stretched 1024x768, on the OSD as you mentioned. Change it to 1366x768 or whatever was the next step down and it would load correctly. Connect it to my laptop and boom, perfect.
I would go through trying to update display drivers, update Nvidia drivers, etc. and some times it would work, but most of the time it made no difference. Then it would suddenly fix it itself, and then a number of weeks/months later it would revert again, for no apparent reason. It's been fine for months now, touchwood...