Note: I am not a lawyer and the below is my personal interpretation of the license terms and the sites terms of service, an actual lawyer should be contacted for any legal advice.
Let me start off by quoting the relevant sections of the license here.
Section 3(a)(1)(A)(i) (Removed punctuation / newlines to easily quote specific subsection only):
If You Share the Licensed Material (including in modified form), you must retain the following if it is supplied by the Licensor with the Licensed Material: identification of the creator(s) of the Licensed Material and any others designated to receive attribution, in any reasonable manner requested by the Licensor (including by pseudonym if designated);
Section 3(a)(2):
You may satisfy the conditions in Section 3(a)(1) in any reasonable manner based on the medium, means, and context in which You Share the Licensed Material. For example, it may be reasonable to satisfy the conditions by providing a URI or hyperlink to a resource that includes the required information.
Section 3(a)(3):
If requested by the Licensor, You must remove any of the information required by Section 3(a)(1)(A) to the extent reasonably practicable.
For users requesting deletion of their own account Section 3(a)(3) applies as by requesting deletion they are agreeing to anonymize all their posts.
For users deleted / destroyed by moderators / staff the important point here is that when the user exists the attribution requirements are satisfied by the user's username (A pseudonym as far as Stack Overflow the company is concerned) and a link to their profile. Now when a user is deleted they no longer exist on the site, for the purpose of other legal requirements their username is also disassociated (The site used to keep them at one point of time), due to this the site must attribute them in some other way or as it is actually done by another pseudonym.
Here we need to consider that the username was one of the pseudonym's the user had on the site, another (much less used by public) pseudonym they also had was their user ID. What Stack Overflow is relying on here to meet those attribution requirements is this user ID, when a user gets deleted all their posts get attributed to "userXYZ" where "XYZ" is the user's ID.
They don't need to worry about using the user's actual name / username as section 3(a)(2) provides them plenty of leeway given it states that the conditions may be satisfied "in any reasonable manner". Furthermore another point to be noted is that there was no explicit agreement between Stack Overflow and the users about the manner in which Stack Overflow will provide attribution, so they can basically give a unique identifier to the user on the site and use that to attribute them.
To state it in other terms the original attribution was of the form: user on the site Stack Overflow having username "placeholder", with the link to their profile being "link". After deletion of the user this becomes: Former user of the site Stack Overflow that had user ID "XYZ". This given the "medium, means, and context" (from Section 3(a)(2)) can potentially be considered as a reasonable manner to satisfy the attribution conditions.
Obviously if a user sends the company a request asking them to attribute all their posts in a certain way, even if it is a deleted user Stack Overflow might be required to do so due to the "in any reasonable manner requested by the Licensor" part in Section 3(a)(1)(A)(i) (depending on what is considered reasonable).