Counterpoint: Archlinux is 89% reproducible with optimizations enabled. The only thing I see which is difficult to make reproducible is optimizations with a timeout.
Instead of using a timeout, an optimization that can must be cut off if the cost is excessive can keep some kind of operation or size count, where the count is strictly a function of the input. For example, an optimization based on binary decision diagrams (BDDs) can put a ceiling on the number of nodes in the BDD.
