Well, even though no new ???s have been added for him in Adeewa, it still is possible the one in Wajaom is for Pandemonium. Maybe the ??? is a hole that "drops" you into Adeewa or something, which is odd but possible considering Adeewa is located underneath Wajaom. So, although the fight likely takes place in Adeewa, it isn't unreasonable to assume that the new ??? in Wajaom could be where you initiate it.
That is the theory Rocl and I were discussing over IRC earlier tonight. There is quite a bit of evidence to support this. You can begin by analyzing various clues in the DAT files. First examine the ZNM pop items. They're arranged in a very organized fashion, something like the following.
Code:
Tier V [Pandemonium Key]
Tier IV [Hydra]
Tier III [Hydra Tree]
Tier III [Hydra Tree]
Tier III [Hydra Tree]
Tier II [Hydra Tree]
Tier II [Hydra Tree]
Tier II [Hydra Tree]
Tier I [Hydra Tree]
Tier I [Hydra Tree]
Tier I [Hydra Tree]
Tier IV [Cerberus]
Tier III [Cerberus Tree]
Tier III [Cerberus Tree]
Tier III [Cerberus Tree]
Tier II [Cerberus Tree]
Tier II [Cerberus Tree]
Tier II [Cerberus Tree]
Tier I [Cerberus Tree]
Tier I [Cerberus Tree]
Tier I [Cerberus Tree]
Tier III [Khimaira Tree]
Tier III [Khimaira Tree]
Tier III [Khimaira Tree]
Tier II [Khimaira Tree]
Tier II [Khimaira Tree]
Tier II [Khimaira Tree]
Tier I [Khimaira Tree]
Tier I [Khimaira Tree]
Tier I [Khimaira Tree]
Now take a look at the seal trade-in items that drop from the ZNMs. Their order bears an uncanny resemblence. The seals you receive for trading them in match as well. The final clue is the layout of the ZNM ??? text in the dialog tables. It follows the same structure, and the text for the ??? that should be for Pandemonium Warden reads "You sense an ominous presence..." This matches the mysterious ??? located directly outside of Al'Zahbi. If it's related, it's an extremely odd placement, but the most logical speculation would be that trading the Pandemonium Key to this spot would warp your alliance to a remote location of Aydeewa Subterrane.