Cryptographic pseudo-random generation of address subsets
It is possible to build a hybrid between your first two solutions, to trade off between their advantages and disadvantages.

Let $E_K : \{0,1\}^{32} \to \{0,1\}^{32}$ be a block cipher with a 32-bit block.  You will select a single global key $K$, that will be stored on every device.  Also, for each device, select a few starting points $s_1,\dots,s_m$, say $m=8$ of them.  These are specific to each device.  The idea is that the device has a pool of $nm$ addresses, namely, the values $E_K(s_1), E_K(s_1+1), \ldots, E_K(s_1+n-1)$, $E_K(s_2),E_K(s_2+1),\dots,E_K(s_2+n-1)$, $\ldots,E_K(s_m+n-1)$.  Each time the device changes its address, it selects a new address from its pool -- either randomly, or cycling through the addresses in the pool, whichever you prefer.  Here you should select $n,m$ so that $nm=X$, so that each device has $X$ different addresses in its pool.

Now you select different start points $s_1,\dots,s_m$ for each device, and select the starting points so the devices' address pools don't overlap.  One approach is to choose each $s_i$ to be a random multiple of $n$, uniformly and independently at random, sampling without replacement (i.e., you discard a starting point if it has been previously selected).  In this way, you can arrange to have up to about $2^{32}/(nm)=2^{32}/X$ devices.

This scheme requires each device to store $m+1$ values, the starting points $s_1,\dots,s_m$ and the global key $K$.  The security you get is pretty decent.  If no device is compromised, this scheme is as good as your first solution (and as good as you can get, assuming 32-bit addresses): it'll take $nm$ or $\approx \sqrt{nm}$ address-changes before a device ever repeats its address (depending upon how the device selects from its pool, either cycling or random selection).  If a device is compromised, not all is lost: you still have some security remaining; in particular, you get security equivalent to a pool of $m$ addresses.

This now lets you tune the parameters to trade off between storage cost vs level of security.  My suggestion would be to pick $m$ as large as you can reasonably afford, given the amount of storage available for this security mechanism.

As fgrieu points out, in this scheme the block cipher must have a 32-bit block size, which is not as common as 64-bit or 128-bit block, but still well studied as part of Format Preserving Encryption, including by Granboulan and Pornin (in proceedings of Fast Software Encryption 2007); Bellare, Ristenpart, Rogaway and Stegers (in proceedings of Selected Areas in Cryptography 2009); Morris, Rogaway, and Stegers (in proceedings of Crypto 2009).  (Paragraph and links copied from fgrieu's comment; my thanks to fgrieu.)