A thir and slightly more minor problem is how to incorporate the Lords of Dust into this. Presumably they know about resurrecting this paladin as much as The Chamber does, and would want to stop this outcome (at least the parts of the Lords of Dust that worship Sul Khatesh). However, the PCs start down that road at level 1. What is stopping the Lords of Dust from just showing up at level 1 and putting an end to all this? There must be a reason they are OK with the PCs at least going on the quest, even if they are more leary about letting them actually finish it.

I suggest turning the "chosen ones" type on its head. There is a separate group of adventurers (much higher level than the PCs) on a similar mission whom the Lords of Dust are convinced are the Chosen Ones. They focus almost exclusively on stopping this other group of adventurers (continually failing, which makes them get even more convinced that this group are their fated enemies) and view the PCs as annoying peasants who will probably get killed on their own. It's only when the PCs are higher level that they manage to capture or kill the other adventurers and realize that the PCs were the real chosen ones all along.