How do altimeters cope with varying lapse rate?
Yes, but it doesn't really matter.

The error that seems to be an underlying assumption in your question is that you're treating the pressure altimeter as measuring altitude. It doesn't.

Rather, it measures the difference between the static pressure and a reference pressure (the latter being the "altimeter setting").

That difference is expressed as an altitude, but it really is a difference in pressure. It could just as well be expressed as just &rho;ref&minus;&rho;static, the value of which would also increase as the aircraft climbs, but that would be less intuitive (and likely less precise, if not necessarily less accurate) especially when close to the ground.

(This isn't much different from how an airspeed indicator doesn't really tell you speed, it tells you the difference between static and dynamic pressure, but the scale is such that this difference in pressure is expressed as a speed. That's why the ASI acts up when the pitot tube is blocked.)

To be airworthy, an altimeter is required to display the correct value to within some margin of error which I don't know the exact value of. Vertical separation is then chosen such that the minimum difference in actual altitude, given the same altimeter setting, between two aircraft is sufficient to ensure vertical clearance between them even if both have instrument errors that are maximally unfortunate.

IMC minimum safe altitudes are also selected in a similar manner, to ensure obstacle clearance even if the altimeter is maximally out of calibration.

Since every aircraft within an area is supposed to be on the same altimeter setting, or (above the transition altitude) on the standard setting of 1013.25 hPa, as long as everyone sets their altimeter properly, the errors will all be very similar and everyone at, say, "5000 ft" or "FL310" is flying at very close to the same static pressure level, even if that level doesn't correspond exactly to 5000 ft AMSL or 31000 ft AMSL. Thus, while you're correct in theory, it is not a problem in practice.