This is not quite incorrect. Some of the NYC taxi re-id demonstrations relied on reversing the hash for medallions, but most have not. In particular, the celebrity tracking did not require the medallion, since each record contains an origin and a destination. The identity of the driver across trips is irrelevant, since it is the passenger who is being tracked. The way this attack worked was to match an origin in the trip dataset to the timestamp on the celebrity photo. This revealed the destination of the trip.
In other cases, no photo is necessary (trips originating or ending at a residential address, linked to another sensitive location such as an abortion clinic).
There is a lot of research available on this topic. "Unique in the Crowd"[1], published in 2013, found that it takes only 4 GPS locations/timestamps to de-anonymize 95% of the population, with no other metadata. With 2 GPS pings, 50% of trips can be de-anonymized.