Writing and reading an ID to/from an Arduino reliably
I'd go with #2. If you are concerned that you will eventually burn-out your EEPROM (100.000 write cycles per ATmega328 ds), try writing a macro, which will dictate at which upload you want new ID to be written in EEPROM. 
Heck, instead of writing all of these onboard, why don't you maintain an offline lookup database and encode things yourself? It would still require writing to EEPROM but you could encode your information in a couple of ints.