If I remember correctly he is still there, but only in the new Reborn city. Gardevoir was way too powerful for early-game (you always using it just confirms it) so she got the much deserved axe. Now you can try some different psychic and fairy types!