stevenz: I'm always amazed how easy banks seem to be to deal with when things like this arise. (Incidentally, I think NBNZ's record was about 30 seconds after hitting the "Pay" button on some obscure asian website to buy a thing before they called me and asked if it was legit.)
Nice that you got a positive outcome.
I've had one occur almost simultaneously with clicking the Pay button before with Westpac. I clicked the button, got a Decline notice immediately, followed by the phone ringing, with Westpac enquiring as to whether the transaction was me, and once confirmed it was, they asked me to re-try the transaction, which went through (apparently they had blocked that merchant so that a fraud rep had to be on the line with you to approve the transaction or it would decline).