...except the device doesn't with the keys, but with the seed (BIP32/Electrum). Device don't store private keys or any metadata for particular addresses.
However such metadata can be stored on the computer, using master public key as a wallet identifier.
Edit: Device can teoretically store timestamp of the seed generation, as some quick-and-dirty workaround. However this still must be provided by the computer, which will probably just ask the user.
I've been battling this concept in Armory with its deterministic wallets, for a while. I implemented "blockCreated" and "timeCreated" variables for each address, but I have been hesitant to actually use them for anything. Because, I determined that getting it wrong was not worth the performance benefit of when it is right: if you trust the timestamps are created and stored correctly, but it turns out that something was wrong (incorrect clock when it was stored), the user could be missing a big chunk of their wallet and it could be a mess trying to figure out what happened (during recovery of a deterministic wallet, that is). Plus, even if it is right, unless the user knows exactly how much they had they don't know that it's right unless you do the full scan anyway. At least for right now, doing the full scan isn't that much more cumbersome than a partial scan, so it's easier to just do it.
I don't know how the HW device will be dealing with addresses (or what is possible memory-wise), but I have found it extremely useful to store the keys even though they are derived from the root. Not only does it allow me to store birthdays and comments/labels, but (most importantly) I can search for an address and know if it's in my wallet without re-doing all the computation. If it's possible to at least maintain addr160 list in non-volatile memory, it will make everything quite a bit easier.
I am hesitant to "endorse" requiring key-indexes to be included in the TxDPs (as I call them in BIP 10, perhaps another phrase+acronym would be better). The reason is to do with multi-sig, which makes sense to accommodate here -- since there's like 90% overlap between what's needed for offline wallets and multi-sig. There will be situations where the TxDP will be created by another party who doesn't have your watching-only wallet, they are only supplied a public key to include in the transaction. They don't know how to specify what your address index is, and your offline device will have no way to detect what public keys belong to you. I guess you could have an optional field so that your online computer could "amend" the TxDP with your address index, but that sounds complicated.
I know it sounds premature to think about multi-sig for your HW device, but I don't think it makes sense to over-complicate that use case if it can be avoided. If we must accommodate devices that can't even store their own address list, then we have to deal with it, but it's worth trying to avoid. And in the end, even with 5000 addresses, that's only about 100 kB to store a raw addr160 list...