I'm guessing either it's a rare spawn or I'm just having crappy luck lol.
For what it's worth I believe you are able to get him to spawn much more easily in the library as I believe there are more PH-type sarnaks in there as opposed to the palace entrance. So if you have a way to get yourself summoned/picklocked through that door it should be easier to camp.