Perhaps grab a recorder and make a trip to a few outdoor markets and layer those. Can't beat actually going out and getting the recordings! I know it won't be much like the markets in the middle east but it might give you a start. You could also go through sound websites and see if there are elements that you could use.

Definitely recording the real thing or using a recording of the real thing or something that's convincing enough. If it has to sound realistic, it could be difficult to make it sound convincing even with a recording from for example a western marketplace.

Experiment and have fun with it. What comes to my mind are three specific layers. Go record a crowd layer. This could be say, a talkative crowd waiting for a seminar to begin or after a choir concert is over. Then record yourself + friends letting out the occasional shout of something "middle-eastern" sounding, as if you are all peddling your wares. Then, find some "middle eastern" music appropriate to the locale, and place that in the distance to add a more festive feel and to reinforce the setting.

I'd agree with the other posts in saying that recording an actual market place could be the way to go. Not sure where you're from but if you're near a big city there might be some ethnic areas where you could get some realistic crowd walla type stuff even though you're not in the Middle East!

Try Audioease Speakerphone.