How does path-dependent gas consumption work?

Offline gas estimation is not an exact science. I have heard people say that it's due to the effect of earlier transactions and/or 'environment' variables like block hash that you don't know beforehand. I don't really grok how this works though.

I can see how computation that is dependent on the value of certain memory slots will be affected if you change those slots. Is this the whole explanation though? Or are there other factors, like caching? Like if a previous transaction accessed a slot, but didn't change it, does that matter? If you know you insert a tx at position 1 on top of the chain and you somehow know the next block hash and the timestamp and the coinbase etc. could you perfectly estimate gas usage? What if you build on top of the chain and you only access contracts that don't reference any environment variables, could you do perfect estimation then? If I know two subsequent transactions never access the the same memory slots, does that mean that swapping their order doesn't change their total gas consumption?

Any literature on this would be highly appreciated!