Let's say my opponent goes to apply claim for an intrigue challenge. I play Vengeance For Elia and give the claim back to them. Then, they play Trial By Combat turning the intrigue claim into a military claim. I know that the RRG says the last claim replacement is the valid one, however, does Vengeance For Elia still mean they have to satisfy the claim even if they play Trial By Combat?

These two cards are both claim replacement of the same level. In this scenario, Trial By Combat will completely overwrite Vengeance For Elia, so the defender will have to satisfy military claim.