Rescuing the Hostage
If the characters agreed to recover the sarcophagus of King Kush and return the king's specter to Prince Keshan, they need to decide how to accomplish that task. Direct confrontation with the Malik is dangerous. Attacks in court will draw a violent response from most of the attending 'afarit. The Malik's champion, Afdal-Kathir, and his counselor, Za'al-Zoresh, immediately attack. If the characters manage to defeat the approximately 100 jinn that defend the Malik, they have a day before the Daimon can reconstitute his Malik Aspect. If they are not out of sight of the City of Brass by that time, the Malik musters every 'afrit in the city and attacks.
Characters might try to target the hostage directly. King Kush's specter is bound to the red carnelian throne with magic similar to Solomon's. Unraveling the bindings requires knowledge of that non-Hermetic magic. If the characters have such knowledge, unlikely but possible, consider the binding a level 75 effect.
One way to liberate King Kush is to get the Malik to release him willingly. There is no bargain he will agree to, no service the characters can perform for the king's specter, so they have to resort to trickery or coercion. One way to trick the Malik is to get him to offer the characters the granting of a single wish as a reward for some sort of service or overcoming a challenge arranged for his amusement. Coercion may be difficult against such a powerful magical being. However, if the characters are able to take his daughter hostage, or able to cause tremendous havoc in his city, and if they are powerful enough to stand against him, they may be able to force him to capitulate. Whatever the terms of the hostage's release, the Malik will certainly be enraged and demand that the characters leave his city at once.