Trying to finalize the quest with Heza (water price), i was riding around the Fae Rhan Palace at least 5 times without finding Heza.

As by chance i went upstairs to the Palace, i saw him standing there. So if someone can't find him, just look here. Of course i had already cleared that place from the soldiers before ;-)