Everything above rests on the operator holding nothing but ciphertext, which is what makes “we cannot produce it” a structural answer rather than a policy. NEX_MAILBOX_DIRECTORY changes that: with it on, you hold a current table of labels your users typed. Labels are human-chosen, so they will contain names, and a table of names is personal data in a way an opaque queue identifier arguably is not.
Concretely, that means access and erasure requests you can actually answer, a lawful basis you have to be able to name, a record in your risk assessment, and a row in your data-retention statement. It also means the directory is a thing a legal demand can ask for by name and you can produce, which is not true of anything else on the service.
The design keeps the cost as small as it can be: a listing is a random handle, a label of at most 32 characters, and an expiry of at most 24 hours; nothing in the stored row identifies a queue; reads cost a single-use server token and are rate-limited; labels and handles are never logged. What it cannot remove is the join between a label and a queue. Two separate things give it to you: a listing published at the same moment a queue receives mail is inferable from timing, and the publish request itself carries the queue identifier in its target and the label in its body, so it is directly observable to you at the moment a listing is published. Not logging it is process discipline you are choosing to keep, not a property of the design. Leave it off unless you have a reason.