I don't know about the specific answers to your question. But, this is what I would have done to get around this:

1) Change my CC Billing address to a US Address. Surely you have a friend or relative whose address you could use simply for the sake of this.

2) Redeem your e-cert with your now US Based Credti Card. Book your ticket.

3) Change your address back to your overseas address on your Credit Card account.

I lived in Dubai for a while, and many e-commerce sites had this similar restriction, especially when it came to zip code. So I did this all the time.