Thanks for the input @sjors – I’m aware of these issues and am planning to use deterministic block templates, as described here.
Each bead (share-chain block) will be able to add bitcoin transactions to a “committed mempool”. From there we will use a deterministic algorithm to select from this committed mempool (e.g. “highest fees” or “lexical ordering on txid”). This way we don’t need to propagate transaction or block template data in shares, as it can be computed independently by all nodes. We don’t have to actually update the UTXO set though, since most shares are not bitcoin blocks.
Yes this means each bead has its own mempool, though most transactions will be shared among them. So we need to be able to do a fast diff/merge between the mempools of different beads.
We’re going to have to deeply investigate the cluster mempool and thanks for the UTreeXO pointer, I’ll take a look. Contributions welcome 
If we have to write our own UTXO management code instead of calling bitcoind…then that’s just what we’re going to have to do. I’m a big fan of libbitcoin’s approach and will emulate it as much as possible.