I suspect one could make one of the timers keep a suitable count in the background (perhaps that's what AltSerial does)
Yes, that's pretty much exactly what AltSoftSerial does. The hardware timer automatically increments at the full clock rate. Each time the input signal changes, the 16 bit count is captured. That's all done by hardware, so it's accurate to within 1 clock cycle.
There's no calibration of software execution time. The input signal's timing is measured directly and simple math is done with the captured timer values to deduce if the signal was high or low at the center of each bit. As long as the interrupt can respond before the signal changes again (so no capture values are overwritten), the input is measured precisely to within CPU clock cycle.
Unlike SoftwareSerial, where varying interrupt latency (eg, if the millis or normal Serial interrupt is running) causes reception of all the bits to begin late and sample off the center of each bit, using the timer's input capture achieves perfect accuracy because the timer's dedicated input capture hardware stores the rapidly increasing timer's value at the exact instant the signal actually changed, rather than when the interrupt code later responds.