I love the insight around cross-shard operations 
I want to push back on the bold part of the statement. The only thing collators care about is getting paid for including logs into collations. As such they only need partial statefullness to extend so far as to guarantee payment. A minimal stateful setup for this is a payment channel where payment is conditional on a Merkle proof of log inclusion.
In that scenario the collator couldn’t care less about the concrete up-to-date application state. It suffices for the collator to know the state of a single payment channel. (I’d argue the cleanest setup is to combine a log shard with a Plasma/Raiden/Lightning-like pay-for-inclusion system in a separate chain.)