Would miners have an advantage by proceeding randomly? If most miners are looking for solving their proof of work in a prescribed order (perhaps preceded by a prescribed way to break down the search space, e.g. by dichotomy); is there not an advantage for a miner (especially a low hash power one) to proceed randomly and try to avoid common search space enumeration patterns where it will be more competitive?
Essentially, everyone is already proceeding randomly, and there is no common search space.


When miners are trying to find a block, everyone works on a different set of candidates: The block reward is paid out through the coinbase transaction. The coinbase transaction's output is specific to the miner because it includes the miner's address as recipient. The coinbase is part of the transaction set that is used to derive the Merkle root. The Merkle root is included in the blockheader. Ergo every mining entity works on different block candidates.
SHA-256 is a cryptographic hash function. One of their properties is that any change in the inputs will cause a completely different output. There is no predictable relation between the change in the input and the change in the output. Therefore, you cannot predict where you will find a block – any new candidate whatsoever could be a valid block. This means that there is no progress towards finding a block, there is no stack of work to power through – it's just random chance. The only way to predict whether a candidate will resolve to a valid block is by actually testing it. 


Hence, the only thing that matters to every miner is to check as many unique candidate as possible, meaning that (beside faster hardware or quicker calculation of the hashing) it can only be sped up by making it as fast as possible to iterate through candidates. That's why miners prepare a blockheader and then for the most part only increment the nonce, extranonce, and the timestamp.