> Report your old card stolen, and renew the card.
As someone who shops online at a much wider diversity of vendors than amazon.com, My card actually gets compromised about once a year and needs its number changed. I don't mind the hassle because it forces me to update the payment method for my recurring charges. On more than one occasion when I re-evaluated whether I really still needed some random subscription, I decided that it wasn't worth it any more to me.
On that note, I'm amazed how many accounts with outstanding balances have been next to impossible to close out by simply sending a physical check to an address. On the phone, they insist, "If you'll just give us your new credit card number, we'll get this all taken care of now." I respond, "I'm not giving you my credit card number because I don't trust that you'll actually stop charging me. I'm happy to send you a check in the mail to pay off my balance." Then it's often, "Uhhhhh, I don't know how to do that. My computer program requires that I enter your credit card number in this field to process. Please just give me your credit card number and stop making my life so difficult."
By the time everything is said and done (and escalated), they always end up finding a way to accept a check in the mail.