Are most algos for nonce + hash generation formally proven to be completely random?
Yes, there's no other way but to check randomly.
Is there a more effective method to generate nonce's rather than random brute force search?
No, see above.
Has anyone done any research on nonce / hash patterns?
There are no patterns. There's no other way to find the hash but to randomly try different inputs to the hashing function.