> but by a "customer" whose credit card number had been stolen somewhere and who saw on his statement our company name (I'm not sure how, since the attackers don't complete the transaction)
I detected a hacked database this way. My credit card (a burner from privacy.com) notifies me of any transaction, including pre-authorizations.
Most likely your customer saw the pre-auth show up.