Header compression repair techniques are accomplished, in various aspects, modes, embodiments, and implementations, by a remote terminal (40), by a header decompressor (46) for use at a remote terminal (40), and by methods of operating the remote terminal and/or decompressor, and (optionally) in some aspects, modes, embodiments, and implementations by taking into consideration aspects of structure and operation of a header compressor (25) as well. The remote unit (40) comprises a transceiver (42) or the like which receives, over a link (36) such as an air interface (38), packets including packets having headers which have been compressed and packets which are potentially out-of-order. The header decompressor (46), upon detection of non-receipt of packets anticipated in a flow (34) of packets over the link, stores, with respect to each non-receipt, a snapshot of header decompression context information existing at the non-receipt. Then, when the header decompressor detects header decompression failure for a subsequently received packet, the header decompressor determines (e.g., by executing a repair process) whether header decompression of the subsequently received packet can be achieved using one of plural stored snapshots.