As many of you correctly surmised, this is an instance of Game Play Error – Missed Trigger. It’s a somewhat unusual case because Gift of Immortality creates a normal trigger that must be acknowledged upon resolution, but that trigger creates a subsequent delayed zone change trigger. Noticing the initial effect does not make missing the second a Game Rules Violation, as some have suggested, because the second trigger was successfully created, even if the players forgot to resolve it. And because there is no GRV, Arthur cannot commit Failure to Maintain Game State.

No warnings are issued, as this trigger is not generally detrimental.

As for the fix, many also correctly identified that, as a delayed zone change trigger, Arthur does not choose whether or not put it on the stack at all, but only whether to do so now or at the start of the next phase. If Arthur chooses to resolve the trigger immediately, it just resolves. Otherwise, as we are currently in the Declare Attackers step of the Combat Phase, as indicated by the recent resolution of Brimaz’s trigger, the next phase will be the second Main Phase. If Brimaz does not die during the remainder of the Combat Phase and Gift of Immortality is still in the graveyard at that time, Gift will return to the battlefield attached to Brimaz. As normal with the Gift trigger, if either Brimaz or Gift has been removed from its respective zone, the trigger will do nothing upon resolution.

One last note is that we want to avoid overtly reminding the player that if he chooses to resolve the trigger later, he can kill the creature or exile the enchantment before it comes back. Just present Arthur the choices of “immediately or at the start of the second Main Phase.” If you suspect either player is making bad assumptions about what will happen at the start of the second Main Phase, just hang around by the table after finishing your ruling to help resolve the trigger correctly.