Randomness is a tricky issue. Are the Bitcoin proof of work solutions truly randomly distributed in the search space? If not, then just incrementing the test may be a suboptimal solution and a random test more efficient. I'm unclear about how many possible combinations there are to test in Bitcoin. Surely there must be more than 232?
There is an infinite number of possible inputs. Any inputs is equally as probable to produce the desired hash (unless SHA-256 is cryptographically weak which there is no indication it is at the current time). Baring some cryptographic weakness it doesn't matter where you start. The only reason to use a subset of the possible inputs would be if you know that certain some range of inputs have a higher than normal probability of producing a solution than other inputs. If that is the case you may only hash certain inputs but even there picking randomly would be pointless. The goal is to attempts as many solutions as possible in the shortest amount of time. You can't think "nonce =rand.GetNext" is going to be faster than "nonce++".
Yes, nonce++ would definitely be faster than any pseudorandom algorithm, except perhaps some clever hardware implementation. But as you say, using random numbers wouldn't improve the proof of work speed.
