When I lived in Shenzhen, there was a Middle Eastern place on Wenjin Nan Lu called Sharazad. I went about four times a week (once, the owner brought back baklava for my pal and I), and dug the presence of salad on the menu. It closed a few months after I finished my contract, but the neighborhood still is the de facto Moslem part of the city. Quite close to the Luo Hu-Hong Kong border crossing (http://goo.gl/maps/vRJKQ).