OP here. My name is unique globally (there are no other people with this name), easily searchable, linked to my personal domain, and my personal email address on that domain.
But even if we can't go by that, I gave them plenty of options that won't involve me disclosing my entire address history. How on earth am I supposed to give all my address history to a company I never heard of, and who shared my data without my consent...
They didn't come up with any concrete suggestions that won't involve disclosing much more information about myself than I think it's reasonable to require in order to release my own personal info.
I think I was very reasonable, and they weren't. Legally I'm not sure what the situation is. IANAL.