Do you consider circumventing the law in your design? Because if you don't, I'm afraid you can't stay away from regulators. I actually can't wrap my head around a non-custodial ATM or locker. Whatever is inside the ATM or locker, the ATM or locker practically custodies. And since that ATM or locker doesn't exist and operate from nowhere, the owner or operator is the one answerable to the law.
The idea where I'm parting from is that of lockers in train stations. Everybody can deposit what they want there, including cash. And there's no regulation requiring KYC.
If we had a P2P exchange where the party who transferred the BTC would then get, from the other party, a code for such a train station locker, where the cash is deposited, then we would already have a part of the idea fulfilled with tools which already exist today. Sure, there are some inconvenients: The cash in the locker may be counterfeit, or there may nothing at all because the buyer wanted to scam the seller. And normally in such lockers you have to pay a fee per hour, which also would have to be paid.
That's the base for the model I'm trying to describe here. Of course the P2P exchange would normally have an escrower. While the BTC seller can prove easily to the escrower that he sent the BTC, the problem is on the side of the buyer. So the seller needs a way to prove the escrower that he hasn't received the cash he expected. A video where he opens the locker would perhaps be a starting point, because at least this way it could be sorta proven if no money was deposited at all, but probably not enough in the case of counterfeit money, which (correct me if I'm wrong) can't still be detected by smartphone cameras. (And of course there's the problem with AI generated content.)
So we need to integrate a specialized counterfeit checking machine in the design, or a third party (e.g. shop owner) in charge of that task.
I'm sure even the store owner and the employee will be arrested by authorities upon tracking that the money used for terrorism, for example, passed through them.
Plausible deniablility would be the answer to this problem, as the "helpers" (shop owner etc.) could claim they can't know the origin or destiny of the money. In the variant with the shop owner/employee checking the money, they typically have surveillance cameras and could thus collaborate with the authorities with images of the suspects in the case there is misuse of the locker mechanism. In theory this takes a little bit of privacy away, but it's quite difficult to escape surveillance cameras anyway so I personally would accept that.