Since Gifts and Favors reads "during your end phase", and the legacy rules read "AFTER your dynasty phase ends", are you triggering legacy holdings during your end phase? Or are you triggering legacy holding during an "in-between" phase?
Legacy Holdings
A topic from AEG's L5R CCG Rules forum, copied for Oracle of the Void from a copy of the forum saved in October 2015, so pages it didn't save are missing. Players' names are left out; the rules officials are named. Rulings are as they stood on these dates; later rulings, the rulebooks and the Rules Archive may differ.
Since Gifts and Favors reads "during your end phase", and the legacy rules read "AFTER your dynasty phase ends", are you triggering legacy holdings during your end phase? Or are you triggering legacy holding during an "in-between" phase?
According the Oracle of the Void, Gifts and Favors no longer reads that ambiguously.
It now triggers "After your End Phase begins" so its timing is definitely AFTER the timing of the Legacy Holding search ability, which I believe answers your question.
If not, feel free to post a follow-up and link this one within it.
On: Gifts and Favors