Interaction of Deicide with Enchanted Evening and the WAR gods
Hi,
Thanks for your question. God-Eternal Rhonas (as well as the other cards in that cycle) have a triggered ability that triggers when it dies or is exiled - it's not a replacement effect. That triggered ability can't go on the stack until the current spell or ability is completely done resolving. AP will completely finish resolving Deicide (including searching NAP's graveyard, library, and hand for copies of Rhonas) before the God-Eternal's ability will go on the stack. The end result is that Rhonas ends up as the third card from the top of their library, not shuffled into a random part of their library.
Thanks,
Nathan Long
Magic Rules NetRep