I like the idea of probabilistic PoS. I think the motivating problem is exaggerated but this could have other advantages too.
Another way (not sure if easier are harder to calculate) is to have the mod of the previous block hash deterministically pinpoint a single satoshi from a coinbase transaction. Then follow that satoshi as it travels from transaction to transaction until it reaches an unspent output. Then that output address will be selected as the next stakeholder. You can do this deterministically. Since the initial satoshi picked from a coinbase output is evenly distributed, the eventual selection will be evenly distributed also. I can explain more if people are interested in how this will work.
I don't think satoshis are tracked the way you think they do. If there's a 50 BTC coinbase which is split to two addresses you can't say "this satoshi went to output A and this satoshi went to output B". Not a major problem though, if you agree on a randomness seed (deterministically from the blockchain) you can simply trace the chain forward, in each step choosing a random output weighted by number of coins.