Sorry about the trouble! Clearly that's not a good thing to have happen - on the plus side, it doesn't happen often, though of course that's no help when it *does* happen.
The checks they do also do also help prevent fraud (which helps reduce costs all around, i.e. chargebacks etc), and they are, as far as I know, good about resolving these issues via email. Usually it's a case of the address on the credit card not matching the country where the order is coming from, or something similar, which they need to keep track of for purposes of VAT, as well. Or - and I'm not saying that this is the case in your case, but it's come up before - something like a fake address being entered.
Again, my apologies!
