You know, just thinking out loud...

Green addresses could be implemented as a second signature in the
scriptSig.

I think this would solve one of the other issues I raised about the green address idea .... you can have some kind of trust aggregator sign the transactions. Merchants like MtGox that send would create a transaction, export it, upload it to the trusted authority which can just check IP address or something to verify it's really coming from MtGox, then sign it and broadcast it.