when it comes to Dubai and the GCC, the options are fairly limited
you can have Co-Pilot
www.alk.com, this covers the whole of the GCC
or, you can use Destinator
or Navigon,
www.navigon.com All of the above engines use one source of maps, which is Navteq.
As mentioned previously, the HTC Touch Cruise Deluxe comes with Co-Pilot GCC Maps. Or you can buy the HTC TytnII, this comes with a tester map for a city of your choice.
The problem you will face is that, the maps of Dubai will always seem to be wrong, because they only get updated once or twice a year... they simply can not keep up with the fast changes happening in Dubai.