About 100 years ago, the Caliphate ships arriving in Schelotto and Fenrecz did so bearing outlandish stories of the disappearance of Kazim-Kazim, rocks, plants and and an eerie fog replacing the stepped districts and Sultan's Palace, with no seeming trace of human habitation left behind. Although these were laughed off as drunken captains overshooting their destination, further investigation revealed that the stories were true, the city was gone, much to the concern of those residents of the city who had been elsewhere at the time of the disappearance.
Multiple expeditions to discover what might have happened proved fruitless, with more than a few never returning at all. Most prudent folk presumed the latter was due to ships lost to heavy seas and other such accidents, although tongues wag about the gods or demons that destroyed Kazim-Kazim continuing their vengeance on those that would seek the Lost City. As time has passed and the city has drifted out of the general consciousness, such expeditions have become more and more rare, with only occasional mad scholars and glory seekers sending ships down the eastern edge of the bay, spurred on by occasional stories of having seen the Palace drifting above the clouds or hearing the cries of vendors drifting over the waves.
Wot Really Happened
Kazim-Kazim was, in antiquity, an independent Sultanate formed by settlers moving out of the East and changed from a fishing village on a naturally protected cove to a major port, a port that served mainly traders coming from the East, lands that were later to become the Celestial Caliphate. Kazim-Kazim grew in wealth and quickly came to the notice of the Celestial Caliphate, who moved quickly to establish a temple there and while Kazim-Kazim remained largely autonomous, the Caliphate's influence slowly grew to the point where Kazim-Kazim was considered part of it.
Kazim-Kazim owed its wealth and odd name to the fact that the city was, in fact and in secret, two Kazims, existing simultaneously in two different planes, the peculiar geometry of the city arranged such that the Palace existed in both with the rest of the cities overlapping, although not literally, as rules regarding building in spaces left open for "spirits" or "gods" were strictly enforced in both cities. It so happened in our particular plane that the Caliphate's interest became too great for the Sultan to bear and with both the independence of the city and the secret of the cities under threat, great magics were spun such that one city left one plane and joined with the other. This caused some problems in areas of the city where building codes were not enforced; however, it generally went without much of a hitch, unless you counted the wholesale slaughter of everybody known to be sympathetic to the Caliphate a "hitch".
While the "disappearance" of the city has largely gone well for those who caused it, there are occasions when the powers-that-be in Kazim-Kazim have need to access to the abandoned plane of reality and at these times, when a heavy fog descends on the shore, it has been said that mysterious ships of well-armed and hardened men slip in and out of where a port might be, going where and doing what, who knows, except that particularly brave or foolhardy adventurers may be able to follow, even into the mysterious fog itself.
(Debts and apologies owned to China Mieville, amongst many others.)