In my thinking about this problem from the IoT space lately, I've been thinking about servers assigning credentials to devices, rather than devices telling you their creds. Assign a UUID and let the device generate their password/key, and the pair gives you a multiplicatively large space.
Your notion is interesting. Anything that automates the client-side is good. People are terrible at managing a security contract 'by hand'
{edit} really, this superstitious notion that random numbers are 'not good enough' is embedded in our programmer culture. Folks continue to use lame solutions instead of just buying into the uuid-as-foolproof-identifier. It totally eliminates whole classes of problems and bugs. And you should be more concerned your computer will be hit by lightening, become self-ware and win the lottery 7 times, and molecularly reorganize into a teacup, before that uuid will be duplicated anywhere/anywhen.
Security is always done in layers, though, and while you're correct that it is extremely unlikely, the chance is nonzero. As such you have to prepare for that and design your system to be resilient to these types of things. In castle terms, you trust that no one will ever breach your wall, but that doesn't mean you don't have guards and an armory inside for the unlikely event it does.