Roger:I phoned Lloyds this morning. They have no record of the card being declined.

matthew_k: I called my bank and complained, and they said the transaction had never even reached them and there was nothing they could have done...

In line with your experiences, I have had Visas declined 3 times in the past 4 years while on trips outside the US. In each case, my righteous paranoia led me to leave the merchant and call the respective Visa issuer within 10 minutes. In each case, they said the card was fine.

Merchants have variable hookups to Visa, whether through a gateway from their point-of-sale system, a service bureau, a direct dial, or whatever. As you suggest, I think some of these failed attempts to validate the credit card never really make it all the way ...and their systems have differing abilities to say something intelligent, so they just say DECLINED!

In part due to this I carry 2 Visas, but I always try to keep enough cash to get me back to the airport if things get dicey!