As a necromancer I hunt all the undead around the spires, I have spent several levels here and Have never seen him once. Does he have a PHer? does he just randomly spawn? does some condition have to be met?
The Plaguebone Overlord spawns in the northwest pyramid in the area with all the pyramids under the giant spires in the hidden valley section of the Dreadlands. He spawns inside the pyramid in the northwest corner of the room inside. He seems to respawn just slightly less than an hour after he is killed, perhaps 57 or 58 minutes or so.
Nothing else spawns inside that pyramid with him, though occasionally one of the wandering skeletons outside will come close enough to the pyramid to agro on you if you are fighting him close to the east door. You can avoid this by pulling him out of the pyramid and away from the areas where the wanderers roam.
If you approach through the east door to the pyramid you will see him ahead of you and to your right as you peek inside the door. I was able to target him from the doorway without agroing him.
He can be snared and rooted, but he sometimes resists spells, so be prepared for that. So far as I can determine he always drops either the Drolvarg Skullcap or the Lost Staff of the Combine, and the Drolvarg Skullcap is his common drop. About 1 in 8 kills (more or less) he seems to drop the Lost Staff of the Combine, though like anything else his drops can be a bit streaky at times.
He's maybe a little tougher than most of the other skeletons in the area, but not so much tougher that a person who can handle the others with ease will be in any real trouble with him.
If you head to the pyramids from the spires, it's the first one on your left.
As a 41 cleric it took all of my mana and divine barrier to kill him. Double attacks, bashes and hit me for over 93. I wouldn't have even been able to kill him at all if my DawnFire didn't proc twice. He also runs at about 20% hp.