In a recent article in the Communications of the ACM, I picked up some URL's for non-English including Arabic.
Here's a list of Search Engines I gleaned from that article:
Albawaba (service overloaded when I tried)
I can't write Arabic so can't do any web searching which makes any sense, but typing in 'manchester utd' yields some interesting results. When you type in queries to Ayna, the characters are displayed on the right hand side, rather than left (Arabic characters go from right to left, rather than left to right in European languages). Trying 'dtu retsehcnam' is fun! It actually brings back some kind of result, but I don't understand it.
I've put these on one page, but will add more Arabic Web Search services as I find them or people send them to me.
Chung, W. (2008). Web searching in a Multilingual World. Communications of the ACM, Vol. 51, No. 3, pp 32-40.
Posts in the series are available here.