Do altimeters for higher altitudes have some kind of clever
mechanism to deal with the non-linearity of pressure at higher
altitudes.

NACA (precursor to NASA) from about 1917 on, did a lot of the early
research on this kind of thing. Here's a link with a great explanation
of how they came up with a clever altimeter mechanism:
http://naca.larc.nasa.gov/reports/1930/naca-report-310/