After you finish the Priest quest, Nalzok may appear once more, randomly in Gehennom, since you didn’t actually kill him the first time, just banish him.