If you know that the drive for the motors are directly linked and isn't slipping, I think an encoder of some sort on the output is the most reliable way to go. You could even just through in a pushbutton to zero at some point and a simple quadrature output should give you very accurate feedback even if the motor control isn't as reliable.
Ultrasonic is alright, but to get that fine of a resolution and that level or repeatability, you may need to get specialized transducers with temperature compensation or something.
IR reflectance could be a good alternative to an encoder, as you could put something like one of those combined sensor modules and embed it in or partly covered by the legs of the desk, making it more immune to interference. At that point you'd need to calibrate the output to distance, but it should be reliable provided you're always shining on the same target surface.
Depending on the construction of the desk, there could be a capacitive option too. Something like a plate attached to the top leg and a plate attached to the bottom leg, and as they approach each other and overlap, the capacitance goes up. You'd have to protect it and it would be susceptible to changes in environment so it could be difficult to stay really repeatable, but you could at least get good relative readings while you made the adjustment.
Digital sensors, be it mechanical switches or whatever, of course, is the simplest option. If, for example, you made a mounting bracket to adjust the height of the switches, you could get an extremely repeatable two position sensor that doesn't even require any real logic to drive.