This is interesting, although I believe that it's impossible for a malicious merchant to discredit a trusted address, because they wouldn't be able to sign the transaction properly. However, this brings up another idea, rather than encode the evidence of a double spend into the blockchain; why not a side-channel method of submitting the offending address and proof of a double spend attempt to a dedicated server for the purpose. Since a double spend transaction doesn't propogate across the entire network, a side-channel method is necessary. Perhaps a second, dedicated IRC channel. Or better yet, a flag that permits the victim to send the evidence across the network already tagged as proof. In this way, clients that receive the proof can check the proof themselves and compare it to their own blockchain to decide if the expensive address can no longer be trusted. In this way, a database of 'burned' addresses can be compiled and shared with new clients in like manner.
This is actually pretty brilliant. It's a dynamic green address scheme using "proof of cost." I believe you're right, the extra step of broadcasting the transaction to the network isn't 100% necessary assuming the merchant actually wants her money and/or the sender keeps track of spent outputs in his wallet in order to prevent unintentional double-spends. The extra check should be to see if the OP_DROP-based transaction actually contains double-spent outputs. That way, both versions of the transaction make it into the blockchain. If there's no double-spend but an OP_DROP-based transaction makes it into the blockchain, then you know the merchant is malicious because there's no double spend and she can actually spend that transaction at any time.
A potential problem involves the expected price deflation of Bitcoin. Imaging I have a stash of a few dozen BTC. They're cheap now; about $4. Imagine I buy about 10 of them, and "proof of cost" 10 different sending addresses. It costs me $40 total. Now, in 6 years, one BTC is trading for about a million dollars. I can double-spend myself almost 40 pounds of gold bars (at today's rates; maybe as little as 20 by then but still far more than $4 worth) per address.
A potential solution would be time-limiting the life of the proof-of-cost trusted address. This way, with the expected price deflation, the cost of the double-spend would still be closer to the maximum value of the double-spend. If I spend $4 today and it's good for a year, I can't necessarily expect to get a million for it at the end of the year.
This is a great way to buy reputation for a mobile wallet that you carry around to retail stores, vending machines, tollbooths, etc. I wouldn't use it on a major savings wallet, obviously.
Edit: This may be completely unnecessary, though. The reason BitInstant charges the rates they do is due to the interface with the traditional banking systems. When Bitcoin is in wider use and the traditional banking systems are obviated, intermediary payment systems built on top of Bitcoin should be expected to charge far less.