I just noticed that HeapTupleHeaderAdvanceLatestRemovedXid is comparing Xmax as a TransactionId without verifying whether it is a multixact or not. Since they advance separately, this could lead to bogus answers. This probably needs to be fixed. I didn't look into past releases to see if there's a live released bug here or not.
I think the fix is simply to ignore the Xmax if the HEAP_XMAX_IS_MULTI bit is set.
Additionally I think it should check HEAP_XMAX_INVALID before reading the Xmax at all.
--
Álvaro Herrera (from some crappy webmail)