I googled amazon customer service and got a phone number. I called the phone number and they concluded what I did, which is that no order from my account has ever gone out to that address. I declined the offer to change my password. They explored the possibility that perhaps I had shared me login credentials with a family member or friend (nope -- well, that's not entirely true. But my sister only uses my login credentials on her kindle). They are going to research whether this has ever happened to anyone else and send me an email.
I have two theories. The best theory is that someone in customer service modified the wrong account. The weaker theory is that there's a really weird bug somewhere deep in the layers between me and an oracle table somewhere.
My concern is that there are some minor security implications to having addresses in my Amazon address book that I don't know, especially if they are okayed for 1-click or have payment authorized.
ETA: Amazon customer service did eventually email me a followup that was a template for how to change my billing address. This is not exactly atypical of Amazon customer service with a very nonstandard problem -- close the ticket and let someone else deal with it if the customer cares enough to contact them again.
I ran across a bunch of coverage of a different Amazon scam involving getting customer service to mail replacement items to different addresses, but that doesn't appear to be directly relevant to my situation. I've deleted the mystery address, which I am not going to blog because I am almost entirely certain that the person is not a scammer and this is some really weird error. (It's a real address in Toronto, with a landline to Toronto, and I'm able to find a guy with the same, not entirely common name, who has a blog and a linked in and so forth that appears to match the address. I'm sort of tempted to contact him and ask him if he happens to know someone by my name, because my first name last name combination is common in Commonwealth/ex-Commonwealth nations.) I used google to look at the building in the address (and the windows which are on the same floor as the address, which includes "Suite 301", and the most suspicious thing about it is that at ground floor there's a Vodka bar called "Pravda". Which isn't particularly suspicious.
I've been through my digital orders for a few months back to make sure there isn't something weird going on there, but I am finding absolutely nothing suspicious. *shrug* Oh, and I started an order to the address, but was blocked on the item I had picked (3rd party didn't ship out of the country), so I switched to Amazon physical book and that got me through to the payment request page -- so the address didn't even have an authorized payment associated with it.
I guess if this is the oddest thing I ever have happen at Amazon, I should be happy. This is way less painful than when we discovered years ago that changing your default address didn't (then) automatically change your gift shipping address -- that had to be changed separately (grrr -- I believe they have fixed this since then, it was quite a while ago).
ETAYA: Hey, cool! At that address was Alacrity, Inc., and that company name appears in the LinkedIn resume for the guy I found. I now feel like I am inadvertently stalking someone.
ETA probably the last time: I've now dug through my digital orders and devices, in search of any possible leakage to a device that was registered to me but not in my possession. I am not the best person about deregistering the kindle app on devices when I pass them along, so I took this opportunity to do that for everything that I didn't have any more, and provided more informative names for what remained. I guess it was a worth while security-on-amazon/kindle apps audit, if nothing else.