Hi AngelNoah,
I googled, and found this:
cic.gc.ca/english/information/security/police-cert/mid-east/united-arab-emirates.asp
Sounds like something that will take a bit of time.
If there is an embassy close by, try that. I had to get a police certificate from Turkey and was dreading that whole procedure, but it ended up being really easy. Luckily there's a Turkish consulate in Toronto and after applying in person (and for no fee!!) I had my police check within a week!
Also, and !!please please someone correct me on this if I am giving bad information!! if your application is completed and the only thing you are still waiting on is the police reference check, send the application off! You can always send the police reference check off once you receive it and have it added to your application.
Rusty - thanks for adding me. I haven't applied for a OWP, but plan to once I get stage 1.