Couldn't postgres reserve a special XID that is never available for normal transactions but that indicates that any transaction can see it because it is so old? Then instead of constantly having to freeze old XIDs each time the XID is going to wrap, vacuum can just set it to the special XID and never touch it again unless something really changes.
It changed in recent versions (9.3 or 9.4, I don't recall exactly which) and moved to tuple header, but what you described is exactly what was done, the xid was 2.
Anyway, an already frozen tuple won't be "re-frozen" again.
Regards,
--
Matheus de Oliveira Analista de Banco de Dados Dextra Sistemas - MPS.Br nível F! www.dextra.com.br/postgres