In late May, 2005, I received a call from Western Union to confirm that I had wanted to send $100 to Rumania. (I still don't understand why they called ... they'd already sent the money, and they weren't going to refund me!)
The thief had done a phone transaction with them, giving my credit card number and enough info to make them think he was me. He also provided a "prior address" (which I'd lived at 25 years earlier, three houses ago).
I called my Visa provider and told them about the fraud. They cancelled the card, sent me a new one (which presumably maintains the length-of-account information which is important in a credit report!), and sent me a form to fill in to claim a refund for the $100. No other security actions were suggested. The new card arrived, with a different account number a couple of days later.
About one month later, I was at a convention, and I made several purchases (from various dealers) using the new Visa. The next morning, one dealer told me that the charge had bounced. I called Visa. Their computer asked me to enter my account number ... and then my zip code (because I wasn't calling from the home phone registered to the account ... some credit card vendors can detect that info!). The computer said "wrong zip code"! I eventually got a human, and explained things. He told me my zip code was X (some number wildly different than it should have been), and that my street address was Y (wrong street, wrong city). Upon checking, he discovered that the address had been changed a week before ... well after the issuance of the new card/number! (I suspect a thief changed the address so that they could get merchandise shipped there.)
(In hindsight, I just realized that I never found out why the dealer thought that the charge had bounced .. Visa told me that it had gone through!)
I changed the address back ... and ... added a password to my account to prevent future changes. The card number was cancelled (again), and a new card was sent to me.
The first fraud handler (in late May) hadn't bothered to mention that ability to have a password put on my account!
Moral: call every credit card issuer you have, and put a password on your account. (And, use a different password for each account.)