When I traveled around UAE & Oman, they still had Borders (and Virgin Megastore), but that was about 5 years ago. Looks like those may still exist: http://www.almaya.ae/our-reach/details.aspx?cat_id=2 I wonder how that works, in terms of distribution etc.
