Simple, except for a slight legacy issue
Withdraw all existing numbers, and issue everyone with a 256-bit code, unstructured except for a check digit or two. Record the new numbers as a QR code on a plastic id card, so that they can be read by standard handheld scanners.
Make it a criminal offence for anyone (including the Government) to store these numbers. Instead, require the number read to be salted with the organisation's name and then stored as a SHA-512 hash value only. The hashed value works just as well as the raw number as a key in the database records for the organisation.
Then (1) the numbers can be used freely within one organisation but records cannot be linked from one organisation to another; the authorities cannot correlate your tax records with your health data using this code. (2) Stolen hashes are of no value to anyone. (3) If a dump of stolen hashes comes to light, it is possible to identify with certainty the organisation whose security was at fault. (4) Banks or other organisations can use the identifier if they like, but cannot link data acquired from elsewhere to expand their knowledge about you.
From a consumer protection point of view, what's not to like? There is, of course, the slight problem that legacy databases will have to be restructured to use a different key. Also, it shifts power away from bureaucrats and corporations to consumers. Oh, that's a fatal disadvantage; it will never fly.