Q:

How to properly anonymize data, if hashing isn't enough?

Today there are news on Bruce Schneier's blog and ArsTechnica about how NY City released information about Cab/Taxi drivers, their trips, and so on.
Basically, sensitive information was simply MD5 hashed. Since the input was limited (3 numbers, 3 letters, at most), it was easy to make some brute-force attack: generate all possible combinations and then do a look-back.
Considering the nature of the information (very small input, to easy to generate all combinations), how could this data be properly anonymized?
Some approaches that have occurred to me::

Security through obscurity (use a "secret" number of iterations) is just security through obscurity.
Append a general, unique salt, would increase the brute-force by 0%: simple append the salt and done.
Appending a unique salt per user, would increase the brute-force, but not too much: take the salt and calculate the 3 digit 3 letters for each salt.

What could be done?

A:

You can use tokenization. Meaning you create a seperate database with randomly generated IDs mapping to 3 numbers and 3 letters. You then insert the token instead of the real identity.
Another option, if you don't need to map the data back, you can use, for instance, a  HMAC (hashing algorithm) with an long random generated secret.  Without the secret you can't bruteforce the original IDs, even when they even only consist of 1 single character.  
Using a HMAC is actually the correct way of using a "secret salt" (a salt is actually never considered secret in cryptohraphy). 

A:

The way to not release the data is to not release the data.
Tokenization wouldn't work very well, because all I have to do to know everywhere and when a driver was is to know anywhere and when a driver was, and then I know that driver's token.
If you don't want me to be able to figure this out, then don't release that data in any form.

