Danke schon einmal für die Antworten.

@kuempi:
Wie Dieter Bender schon beantwortet hat, brauche ich eine eindeutige Referenz u.a. zur Verknüpfung mit anderen Tabellen.

@DBender:
Genau das war das Problem. Der Inhalt des Keyfeldes hat sich geändert und jetzt laufen wir Gefahr, doppelte Keys zu produzieren. Deshal die Umstellung auf eine ID ohne Inhalt.

Ich tendiere auch zur Key-Tabelle, wobei ich im Moment noch keinen Plan habe, wie ich die generierten IDs "feinkörnig" und wasserdicht vergebe. Datum/Zeit/Jobnummer reicht nicht aus, da mehrere IDs in der gleichen Sekunde benötigt werden.
Die Idee mit dem Pool von n IDs gefällt mir schonmal gut.

Ich mache mich mal an die Arbeit, bin aber für weitere Anregungen offen.