Post History

Every user already has an associated unique number (it's in your profile URL).  The easiest way to distinguish user names for deleted users would be to use that number.  This is what SE does.

A consequence of this approach is that this means that anyone who knew your user number before you deleted your account would be able to identify you afterwards.  I don't know how much of a problem this is in light of "right to be forgotten" laws in parts of the world.  Even without a legal motivation, I'm unsure of the ethical considerations.  If people want to be done with us and delete their accounts, should we make them completely anonymous?  The single "deleted user" name does that, at the cost of some confusion.

If we want uniqueness and anonymity, then I guess we would need to generate a new number and associate it with the old (deleted) account.  Profiles are soft-deleted, so that they remain available if needed for auditing, spammer investigations, and so on. Deleted profiles aren't linked and that link you're seeing is a bug, so thanks for the report.