Two years ago I used my 28° in Japan - 2 minutes later I had a call from them verifying the purchase.
Had similar last month with ANZ Falcon; tried to purchase coffee at Starbucks HKG and the Visa was declined, the ANZ issued Amex card though went through ok. They were on it as it was being processed!
They called my home number (sometimes I wonder why I leave mobile numbers??) and had to call back - thankfully they hadn't cancelled the card, just put a hold on it. Was up and ready to go in 15 minutes. Not sure why the info in my account (I live OS, make purchases throughout Asia regularly etc), but the CSO entered it all again, and last week when I was in HKG again, all went without a hitch.
I was worried they'd cancelled the card there and then (has happened before on a Citibank VISA and left me in the lurch), but thankfully brains were used and they attempted to contact me *before* cancelling it.
In this day and age, I'm not surprised by *any* CC fraud - in fact I wonder how much more is done, now that you can just "Pay & Wave" etc - no signatures required. With regard to the OP's card - I'd lay odds it happened at the source, easy enough to do, they only need to grab a few a week and away they go on a little spend spree.
In a way it's rather smart - the card is used *prior* to arrival, so there would be a decent timeframe between the customer receiving the card and the first statement; possibly makes its harder to trace. . . . . .