First use the TID as input for a KDF to generate one or more tag specific keys, using a static, symmetric master key stored in the initialization software and gadget.
Use one of these keys to obtain access. Use another for verification of the tag.
During initialization derive and set the access key (s). Then create a HMAC over a static value (or multiple static values) within or outside the memory of the tag, and store it within the tag.
During read out by the gadget use the keys to gain access and to verify the HMAC value over the static value(s).
This symmetric solution can of course be complicated by several patches with regards to key management (roll over to different keys and such, possibly storing multiple hash values).
That's for a symmetric solution. If you're brave you may consider an asymmetric solution. As you don't have enough room for e.g. RSA signatures you may want to go for a small size signaturea small size signature. The obvious advantage is that you don't need to distribute the private key to the gadgets. These kind of schemes do however require more cryptographic capabilities from your side.
Don't forget to store a version number or something similar in your tags so you have an upgrade path.
