Picked a different RNG than the concept for the first fairy. It's faster.
For the second fairy, I delay exactly 5 frames across various screen transitions in order to spawn the fairy and have it fly mostly where needed. One frame later, and the 21-frame rule would kick in.
Out to the second fairy, I haven't actually ran the rest of the trek to know if the encounters behave on the way to the palace. Still, there's not a lot of possibilities to look at without moving past that frame rule.