I'd spent about 10 hours on the main stairs between 3rd and 4th levels, and thinking this guy doesn't exist. While I was camping him I was spending my time on the 4th floor for higher level mobs.
I was surprised when the undead crusader attacked me on the 3rd level. He was walking from the area with the square hole you drop down to the 2nd floor through, to between the two guards at the top of the 2nd to 3rd level stairs.
Somehow it felt like an accomplishment that I managed 1/6th of this quest after 10 hours. RAH!

Burynai Hide Cloak
Fine Steel Morning Star
Iksar Skull with an 'X' 