Thanks SR90! It looks like gift values above 100$ will incur customs tax in the USA. Also, Fedex will only refund 100$ (for lost packages), regardless of the value of the package, even if you buy insurance. It's sounds ridiculous, but from what I read on the Fedex site it's true. If you do declare a lower value, and are very unlucky, you might run into issues with customs if they find out your shipment is worth a lot more, and they'll charge you customs on the full value.

Looks like the 64GB from Dubai will end up costing me (2599 AED)710$ + 80$(300 AED non-priority Fedex) = 790$. If I get charged customs, it'll be even more. Ouch.

Gerbick: You said Dubai - 16gb Black $683.33 USD (paid w/ shipping)
Prices for 16gb in Dubai seem to be ~640$. Did you manage 45$ shipping?