It's not a problem to keep thousands keys for every device.
In my imaginary situation device doesn't generate random public and private key. It gives the next pair which Ledger company knows
You should stop "imagining" stuff and start to read stuff.
The whole part which handles the key generation / initialization of the ledger is
1) made onboard and
2) is open source. You can chack github and read into the algorithm. There is no hardcoded list of compromised keys. Also there is no communication
to any server during key generation and initialization of the ledger wallet.