Actually, this is in character. People with devour are fascinated by things with special properties. In fact, that's probably why he was here in the first place. To eat bits of the tree and see what happened.
Because you knew of two other cities on a map you found and none of you rolled a check to see if you knew any nearby towns.
eh, my other two points are valid, and I still think it's likely we talked about it while travelling
The info you know about so far (as a party):
The oracle moves a lot
The great tree knows where the oracle is
Whoever had the time bow write in cell-stained blood to find the oracle
For some reason "N.K." let you live.