The general rule is, you never tell someone suspected of fraud why they are suspected of fraud; it will help them figure out how to not be suspected of fraud in the future. You also want to give them as many required telephone interactions as possible. A) this slows them down if they are trying to automate the process and B) It's much easier to determine whether or not someone is trying to defraud your service over the phone.

If the credit card you are using is stolen, eventually the billing company will have to charge back your purchase. Enough chargebacks in a month and the billing company gets a HUGE fine. It is in their interest to err on the side of caution in cases where something like this occurs.