The only reliable way to find all transactions which mention certain address is to scan all Bitcoin transactions.
So this doesn't buy you anything: you still need to read all transactions in block, parse them as Bitcoin transactions, checking whether they mention exodus address. If they don't you can skip further processing step.
This doesn't improve scalability. Maybe you'll have processing twice faster if you avoid "multipart" transactions, but processing time/download time is linear on number of transactions in blockchain.
You might be able to fetch only transactions which mention exodus address if you use centralized service like blockchain.info, but then you will depend on such service. For example, such service might omit a transaction to perform a double-spend on you.
If you only consider 'full node' clients (or ones using similar design), you should be concerned with what they need to keep in db and what changes they need to apply to it, not with number of transactions processed, since full node clients need to process all transactions anyway.
Say, what do you do in case of reorg, i.e. how do you unwind the state back to the point it was N blocks ago where fork happened?
One way to do this is to keep track of all changes to the state, but then you'll store the whole history...
Yes, one way avoid the server-trust problem is to use multiple independent data sources, so they would have to collude to perform a double-spend.
But yes, full nodes will still have to scan the full block chain. However, they should need WAY less RAM to do so, since the vast majority of it can be just thrown out once it is determined to not apply to MasterCoins.
Since unwinding bitcoin transasctions (in event of reorg) also unwinds MasterCoin transactions, I don't think anything would be needed other than a re-scan of the block-chain data.