For the scaling issue, perhaps SSL+WebSockets (or a custom simple TCP thing) is one way to go. You set up long-term connections to a bunch of known-good senders. Then when they broadcast a tx, they also broadcast it to any listeners they have on the WebSocket. So it's push not pull. It can scale pretty well I think.
With this setup, you are putting a pretty big burden on those senders. Let's say there are 10000 websites and shops and whatnot which want to accept transactions from Mt.Gox, then Mt.Gox now has to keep 10000 of those connections open and publish all their transactions over all of those connections just so that the one shop which actually received the transaction knows it came from Mt.Gox.
Of course these types of solutions also then bring you to the question of why not do it all out-of-band then anyway. Have Mt.Gox make a HTTP call to the merchant which is SSL-signed and all that. And I'm not against such a solution, it's just a whole other discussion about how to specify such an out-of-band mechanism which I don't feel like tackling at the moment. But if someone were to design and prototype something like that and that out-of-band mechanism would not be limited to web, but could also work over NFC, then I would be more then willing to implement it for Instawallet.
For the moment I still think, that the fact that green addresses are completely in-band is a pretty big advantage. And I can also see it scale decently. Just some ideas: There could be a public directory of green addresses which point to the respective websites. As a merchant you could decide, that you accept all green addresses where the associated website has an EV SSL certificate. Or there could be a neutral website which manages a security deposit for each green address and basically says: If you can prove a double-spend for a green address, you will be reimbursed using the security deposit. That way a merchant can actually accept totally unknown green addresses, as long as they are sufficiently backed (of course here the merchant has to trust that those security deposits are managed correctly - as you said, the key question is always about trust).
I think the general idea of the green address technique is sound, but it boils down to managing trust relationships.The intention of Bitcoin is to relieve you of that burden.
Approaches based on transaction radars and so on might be a better way to increase confidence in zero-confirm transactions. If you know that 80%+ of mining power accepted a tx, you can assume it will confirm and be reasonably secure.
This "reasonably secure" has - in my opinion - too many limitations to be of much use. Mostly because of attacks where the double-spend transaction isn't broadcasted, but appears anyway in the next block (specifically this scenario:
http://www.reddit.com/r/Bitcoin/comments/kmo2l/suggestion_bitcoin_confirmation_honeypot/c2lhbv1 ). Which prevents a number of interesting applications (like getting cash from an ATM instantly or moving Bitcoins into an exchange quickly). Ok, you might be able to buy your pizza like this reasonably secure, but then again, the merchant might also like to be able to move your payment for the pizza into an exchange right away to sell it for USD. With a heuristic like that, the exchange won't accept that. Green addresses can make it happen (You pay the pizza with Instawallet, the payment is handled by Bit-Pay which could have a green address as well and moved into an exchange that accepts green transactions and sold off immediately.)
And there is a further problem: You will always need to add a couple of seconds to listen for possible double-spends, introducing additional delay. I would claim that this is a pretty big deal for users - for them it pretty much can't get fast enough. So a green transaction can also be of use for the pizza scenario, because it allows you to go as fast as the Bitcoin network will allow without having to introduce artificial delays.
Until an official bitcoin release provides APIs sufficient for sending and verifying green address transactions, I think Mike's proposal is the easiest for vendors to support. There are few enough trusted wallet providers that scaling shouldn't be an issue for a while.
Either approach doesn't work today and will require further work. For Mike's proposal wallet providers would need to start publishing their transactions and for green addresses it needs to be easier to verify those transactions. I'm not sure which one is more likely to happen soonish.
Again, I'm open to other solutions and am happy to accept and implement the group's consensus for Instawallet. Although I have to say, that at the moment I wouldn't be the first to adopt Mike's proposal for Instawallet, as I think it's a solution that will create a user experience that isn't as as good (i.e. fast) as it could be. That extra out-of-band communication will always slow things down and I consider extra latency to be a really big deal.