Maybe he just likes you haha

Deathgaze, in the SNES version anyway, is sitting in a specific part of the map each time, so you have to find him, not the other way around. I don't know if it's the same for the GBA though...