Reading your article, that doesn't appear to be a very correct description; The de-anonymization seems to have occurred through two primary aspects:

1. The taxi medallions were extracted due to poor crypto choice (and simple structure of medallion IDs), so you can map from reality -> dataset

2. The celebrities were photographed entering/exiting the taxi, with the medallion captured.

If you broke the link -- the taxi medallion -- you wouldn't have de-anonymized trips. And NYC anonymization process clearly (and correctly) intended for that link to not exist.

That is, start, end and length was not the key motivators in de-anonymization in this case. However, you can still imagine this data is sufficient to de-anonymize when usage is rare (and you've captured either start or end destination), but otherwise, the taxi data is not indicative of anonymization futility but rather implementation failure.