Is my id obfuscation algorithm secure? I'm designing an id obfuscation system.
My system includes:


Embedded chips, each chip has a unique 32-bit address (id).
Server
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:


The encryption secret key must not be saved on the chips - Some of them may fall into the wrong hands and be reverse-engineered.
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).
You are over-thinking about cryptography. It's not supposed to be that complex.
I started with the idea "let make 1 chip have multiple id".
And I come up with something relatively simple than what you mentioned so far. (I'm not sure if this usable in your situation or not. It's just based on the info you described.)

Prepare: I will make every chip have unique id and a counter like you mentioned.
Setup: When a chip is registered to the server I will make the server generate keyed hash using unique id as key and counter as message but instead of generate just 1 hash from the current value of counter let say I generate 5,000 consecutive hash start from the current value of counter and store generated hashes in the database.
Identify(chip): Instead of directly send the unique id to the server just send keyed hash with the same algorithm as hashes generated on the server then increase the counter in the chip.
Identify(server): The server can determine the chip id just by querying the database with received hash. (This operation should be very fast since hash value can be indexed.) From this querying the server should know the counter value inside the chip too not just the unique id. The server can now delete current and older hash from the database. If hashes in the database for a chip fall below (say) 2,000 the server will generate consecutive hash to fill 5,000 hash pool.
That's the overview. It's seem like I missed 64-bit communication chunk constrain. (Thanks to Ricky Demer for pointing it out.)
To address that issue: the hash used should no longer than 64-bit.
Just allow hash collision happen in the database we can simply don't use hash as the primary key.
When the chip send collision hash just ignore that and wait for the next sample. If the missing sample is significant in some way we can assume that next hash will have the same chip as the owner hence we can pin point which chip send the previous hash. (If it still undecidable just wait for next one.)
Or we can also assumed that the chip that just appear with the collision hash is not the one who send the hash.

This idea is derived from what you mentioned about the counter that leak chip identity in some way but now we use it on the server.
And that's it I will do it this way if no one point out any flaw in this approach (which I myself cant see).