On arabictypography.com, Tarek Atrissi wrote a good and fun-to-read article about the top 10 Arabic graphic design clichés.
I have to agree on the (all dressed in Gold) and on the (I want Al Jazeerah logo too). On the other hand I do not think that the palm tree is a cliché, yes it is overused in Saudi, but not in the rest of the Arab world.
I have always enjoyed building Arabic words out of (deconstructed, rotated, and scaled Latin letters from popular Latin fonts), maybe even when the time comes where we have enough professional Arabic fonts out there, this would still be one of my options.
Enjoy the full article here