Cryptographically secure product keys
Your second solution seems to be quite close to optimal. You perhaps do not need both nonce and timestamp unless timestamp is part of the payload. Anyway, the structure
$$
N||P,
$$
where $N$ is 48-bit nonce and $P$ is a 32-bit payload seems sufficient for your needs, as you are unlikely to generate more than $2^{48}$ product keys. To ensure authentication (unforgeability) you merely add a 48-bit zero string (analogue of your 'magic') and encrypt it with AES:
$$
KEY = AES_K(N||P||0^{48}).
$$
Forgery is unlikely in this scheme unless an attacker makes more than $2^{47}$ attempts (which I also suppose is a fair assumption).

In this scheme you can vary all these parameters if you have a larger payload but expect fewer keys or forgery attempts.