robtillaart:
The reference does suggest using randomSeed(analogRead(0)) (or some unused analog input).
On a 328 you also have analog(8) to measure internal temperature, but it is not reliable random - http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1294239019 - but it might be good enough for your application. It won't cost you a free pin as it is internall so allways free....
If your application has a ethernetshield you might consider fetching the serial number from a simple PHP script on a local website or a randomnumber from www.random.org.
Imho: Sometimes it is much easier to solve things with some extra tools than try to build it all in one sketch.
Thanks Rob, I think I got a workaround for my particular implementation. Since the ID is not needed until the computer first asks for it, I moved it from setup() to loop() and deferred the EEPROM setup code until the computer requests it. I also implemented a crude counter inside loop(), and used the loop count as the randomSeed() when the EEPROM setup code is run, so it is almost impossible that two different bords will call randomSeed() at the excat same loop count. I think that's good enough for my purposes.
Appreciate everyone's help.