I worked in banking and bank security for about a decade, including a job that involved drilling safety deposit boxes.
It’s basically impossible to do what you’re describing without persuading certain bank employees to violate bank policy and possible state law.
The best luck you might get would be getting a weird old key and then asking a locksmith if there were any safety deposit boxes that took that key anywhere in town.
If you got lucky, the lock might be from a very old box and you MIGHT be able to figure out the closest bank that took that type of key.
If you were in a rural area, there might actually be only one bank that still had that particular kind of key still in use.
A possible plot point might be that finding the distinctive safe-deposit ket tells the cops that he had a safe-deposit box. So they can then look through his checkbook or credit card statements to find the payment to rent the box, which will tell them the bank name, and then they can get a warrant. (The warrant would not need to have the specific box number, just say “the safe deposit box rented by John Doe” and the bank would locate the specific box. Many (most?) customers don’t remember their box number anyway, the vault clerk just looks it up by name.)
This won’t work if the person paid the rent on their safe-deposit box in cash, of course.
When I worked at a bank holding company, one of the people involved with boxes said that most people paid for their box by check or credit card, or a direct debit from their account (that was what the bank preferred). He said that when people paid in cash, it was usually something crooked going on – either actual criminals, or something being hidden from a spouse or business partner. Sometimes they tried to use another name, but banks require ID to match the name.
Interesting idea, thanks. But it wouldn’t have worked for that particular story – wow! it was nine years ago! – because the central plot point was, in fact, determining the name of the “John Doe” who’d been found beaten, unconscious, with no id and no possessions except (in the planning) a safe deposit key. Which I’d hoped they could use as the clue to lead to his name, but that didn’t work out because of the awkward reality so many Dopers helpfully pointed out. (Well, he still had the key in the finished story, but it wasn’t what led to his identity.)