AmEx has been absolutely phenomenal the couple of times I've lost my Costco card overseas. Twice in Tokyo I called the night before and was told AmEx Japan would issue me a replacement from their office the next day (the one time I called in the morning they told me they'd have it ready by 3PM). The one time it happened in China I was told it would be rushed by UPS and it got to me within half a week.