I don't fully understand it, but Mike Hearn has written a lot about how you can leverage the power of the chain without actually including your thing in it.
Alright, thanks for the lead - I see that Mike has been quite active, I have a lot of reading to do :-).
Not including the data directly in the main block chain is exactly how I was thinking about it - I believe you simply need to include a hash of the external 'symbiotic' Merkle branch. It's still 'extra baggage' I suppose but it will be a tiny fraction of sizeof(vtx). I'd say the indirect benefit of having these very useful services only purchasable with Bitcoins combined with the extra mining revenue make this quite useful - what's the official take on this?
In fact thinking about it - it doesn't even have to be in CBlock, it could just be a regular transaction with some fancy scripting...
I will now crawl back in my hole and come back when I'm not quite so ignorant, hopefully with some code.