Maybe as a clarification here: the second transaction that pays the extra fees must depend on the first, i.e., be a descendant of the zero-fee tx.