Is my id obfuscation algorithm secure?
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).