Is this idea plausible? Or will the authorities shut all these locations down because of doing something other than what they're registered for?
This is exactly my question too. I think it may work in some jurisdictions and in others it doesn't.
Where it doesn't, other alternatives also don't.
The problem of all ideas here is similar: with the (rare) exception that at the same time there's a buyer and a seller at the same time at the ATM, the cash has to be deposited somewhere, and one would try to avoid someone really being a "custodian".
Thus the idea of the (needlessly?) "complicated" design is that there is no custodian explicitly for cash but instead a set of lockers which would not have a real "custodian", but a sort of insurance company could cover the value in it, financed by the fees.
An even simpler design could be the following one: The lockers (deposit boxes) are placed inside a store, completely independent from the device checking the genuineness of the cash. Once the seller has deposited the Bitcoin on the P2P exchange, he gets access to the locker where the buyer has deposited the cash. The store owner/employee confirms the genuineness of the cash with his point-of-sale devices and gives a code to the seller which serves to sign a multisig transaction, and then the BTC are freed (there could be a small security deposit for the buyer to prevent "just trying" to deposit fake money). This means the store employee here acts as escrower, but not as a custodian, neither of cash nor of BTC.
There is only one problem with this design: dishonest buyers could try to escape with the money while the store employee is distracted. But that would be probably solvable, e.g. by carefully choosing the location of the locker (very close to the checkout).
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.
Somebody will always have to be held accountable. In strict jurisdictions, we know even those who only wrote open-source codes were arrested for something beyond their control. In such places, with your design, although otherwise great, 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.
In which case, there isn't only one problem. The other problem, which is even bigger and perhaps even insurmountable, is the government itself. I'm afraid you can't have a lawful service like this which is also private and anonymous.