To me, double-spending is analogous to passing bad checks. Legally, it's one form of conversion. Conversion includes forgery, for example. In either case you are getting an explicit or implicit assurance from the payor that the instrument is good. That's the case with checks right now. The assurance you mention is, in law, called an "implied warranty", and there are several kinds of them. Implied warranties are creations of law, and need not exist in a newly designed system. The system in which the issuer charges for a deposit attempt needs no implied warranty of validity. A deposit attempt is made, the fee is paid which covers equipment and communication costs, and everyone is happy. The problem is, the fraud doesn't occur (typically) when the note is redeemed at the bank, it occurs when the note is exchanged at the market. Is this proposing to charge the merchant when he in good faith turns in the cash which was given to him by the customer, and it turns out bad? What cruel irony! Here he is already cheated once, and the bank will charge him an extra fee as additional punishment? Fairness is overrated. In the commercial paper world, there is the concept of the "holder in due course", which is a legally protected holder. In certain situations there are parties who have to pay off both the holder in due course as well as having already paid for the note, or in other words, there are parties who incur a dead loss. There is a public policy decision implicit in this doctrine that a protected market in commercial paper is more important than fairness at each stage in the transaction. This is a profound principle. Overall economic benefit was the goal, not individual economic benefit. Now, I should add that if the issuer charges a deposit attempt fee, that a reasonable merchant would pass that fee right along to an anonymous customer. If the merchant wishes to extend credit in the size of the transaction or in the size of the deposit fee, that's their business. So the question of intermediates is really not relevant. An intermediary, the merchant in this case, can derive some source of income by being an intermediary, and either passes the deposit fee along or averages it with other income. The market will decide. Any merchant who must pay deposit attempt fees and who neither passes that cost on nor makes any attempt to otherwise stochastically recover that cost is, well, stupid.
From the issuer's perspective, the system is stable because database queries, that is, deposit attempts, are being directly paid for. From a potential multiple spender's perspective, double spending gets them nothing, and they have to pay for getting nothing. They might be able to convince some merchant to try the transaction for them, but it won't succeed and the only difference is that someone else pays the bank.
But I thought we were referring to a double-spending protocol in which users revealed their identity to the bank. I'm talking about an online system. The idea of charging per attempt might also work in an offline system, if only to get the merchant to pass the fee on to their customers. Eric