I'm designing an id obfuscation system.
My system includes:

1. Embedded chips, each chip has a unique 32-bit address (id).
2. Server
3. Insecure low-bandwidth unstable one-way channels from the chips to the server.

The chips send messages to the server over the insecure channel.
The messages are simple "I'm alive" notifications. There is no meaning to forging messages (no benefit to the attacker).
The server should be able to recover which chip sent which message. However, I don't want attackers to be able to trace specific chips for long period of times, i.e., the messages should not contain the chip's id, but an obfuscated id, which should change once in a while (in my case every ~5 minutes on average).
In my case, $2^{16}$ different obfuscated ids per chip are enough (the obfuscated ids will repeat every ~227 days).

One way to obfuscate the id is to encrypt the id together with a counter. For example, use a 48-bit block cipher to encrypt the concatenation of the 32-bit id with a 16-bit counter, that increases every ~5 minutes.
I don't know of any 48-bit block cipher, but 64-bit block-ciphers, such as Blowfish and Skipjack, can also be used: by encrypting the concatenation of the 32-bit id with a 16-bit counter and some fixed 16-bit value (could be zeros). 

However, there are two more requirements:

1. The encryption secret key must not be saved on the chips - Some of them may fall into the wrong hands and be reverse-engineered.
2. Asymmetric encryption cannot be used ... They take too much time and create too large outputs (over 64-bit).

This means that all the obfuscated ids must be pre-calculated and saved on the chip. It also means that using a 64-bit block-cipher will consume 33% more space on the chip than a 48-bit block-cipher.

Since I don't know of any commonly used 48-bit block cipher, I had the following idea.
For each each, encrypt all concatenations of the 32-bit id with any 32-bit value.
Save on each chip only the results that end with 16 zero bits (obviously, without last 16 zero bits of each obfuscated id).
There should be around ${2^{32}}/{2^{16}}$ such obfuscated ids for each chip, which is exactly the amount I need.

The server will receive the 48 bit obfuscated id, pad it with 16 zero bits, decrypt, and slice the first 32-bits of the result to recover the chip's real id.

The only flaw is that the pre-calculation of the obfuscated ids for each chip is time consuming.

Can you see any flaws in my algorithm, besides that? Do you have any suggestions to improve it?

Another approach was to use 32-bit block ciphers (skip32), and call them several times so all the 48-bits are used. However, from what I learned, 32-bit block ciphers are considered obsolete.

Furthermore, if you have any suggestion that includes a stream cipher, please notice that the channels are unstable and messages may drop - CBC mode will not be recoverable on the server side. CTR mode that includes sending the counter is also problematic, because an attacker can trace a chip merely by watching the counter in the messages - if a message's counter is 123, and 5 minutes later I see a message with a counter of 124, it probably originated from the same chip (syncing all chips is not practical).