A couple more thoughts about Malakim civ. It seems to be moving toward an arabianish feel, desert nomads and such, and I think that'd be cool. Analogous to the Lanun, focused toward one area, but through a different mechanism so they aren't just the Lanun of the dunes.
An issue as said is how can you encourage them to build in the desert without simply making desert tiles act like plains for them, because like Corindale said, deserts aren't going to give food to anyone. But you need food to have a city of any size. Desert peoples, to my knowledge, have been nomads and traders mostly. Here are some possible mechanics toward these ends:
1) Half of all trade route profit for Malakim cities is gained in food instead of commerce. This would allow them to grow without needing to rely on working terrain or springing all the tiles.
2) Remove health bonus from forests. This is a less harsh way of preventingthe trade route food bonus above from growing non-desert cites too fast too soon.
3) Make desert tiles provide one extra production. Malakim workers can't exactly feed themselves from cactus, but they know how to survive the heat to get at the resources there.
4) Whenever a city would lose a person (population) to either starvation or an attack, that person doesn't just disappear, but is moved instead to a random city connected via trade routes. (or maybe 50% chance). This may be a Malakim city, or else an allies with OB-in which case the citizen would retain it's nationality, making it harder for that civ to wage war against Malakim. (unahppiness form "we don't wanna fight our motherland") Limit this transfer to once per city per 10 turns or so to prevent abuse. This would represent nomads being willing to follow the food.
5) The malakim population fed by trade routes makes them another good candidate (Kuriotates and Gregori being the others) for great person strategies, as these people are either mining the deserts or specialists. A small synergy bonus for this could be allowing GP super specialists to leave a city as in 4 if the city is destroyed if that city has a trade route to another Malakim city.
6) A Carrot and stick method to make deserts attractive, rather than just possible, is needed. I'd enable any desert tiles in the city radius (regardless of what cultural boundaries it lies in--this is a gift from the sun god above, not the earth) to have some effect when an enemy enters it. More common than ancient forrests, as those also have great production value. It could be a 25% chance at a sand lion, but that is similar to the fellowship Treent summoning. It could be a dramatic health degen, like 10% per turn, but would the AI know to move? I think that was mentioned with regard to a recent wonder proposal. How about summoning a sandstorm, which is a weak unit that causes collateral damage and may push the attackers away, like tremor spell. To make this defense needed, give thier cities 10-15% less defense bonus no matter where they are.
6.5) Replace their pagan temple (he doesn't seem like the type to like pagans) with a special "lightbringer temple" that increses the sanstorm or whatever.
7) Perhaps a Malakim only Oasis improvement, a "bazaar" that adds +1 hammer, +2 commerce, and provides a spices resource or a happy face.
8) Maybe an extra withdrawl chance for their calvary units when attacking into deserts as well, they disappear into the sandstorms.
Okay, well, pick and choose if you want, or just pick apart and tell me I'm in the wrong direction!