Solution:

It suffices to show the upper bound and lower bound.

Upper bound. Loosen the restriction on $y$ to $y \leq 24$. We'll reduce our remaining possibilities by binary search; first, query half the grid to end up with a $10 \times 24$ rectangle, and then half of that to go down to $5 \times 24$. Similarly, we can use three more queries to reduce to $5 \times 3$.
It remains to show that for a $5 \times 3$ rectangle, we can finish in 4 queries. First, query the top left $4 \times 2$ rectangle. If we are left with the top left $4 \times 2$, we can binary search both coordinates with our remaining three queries. Otherwise, we can use another query to be left with either a $4 \times 1$ or $1 \times 3$ rectangle, and binary searching using our final two queries suffices.

Lower bound. At any step in the game, there will be a set of ordered pairs consistent with all answers to Philena's questions up to that point. When Philena asks another question, each of these possibilities is consistent with only one of YES or NO. Alternatively, this means that one of the answers will leave at least half of the possibilities. Therefore, in the worst case, Nathan's chosen square will always leave at least half of the possibilities. For such a strategy to work in $N$ questions, it must be true that $\frac{460}{2^{N}} \leq 1$, and thus $N \geq 9$.