It is exactly the right thing to have a deletion request management system. In fact, given the importance of this function, the timeframes for response, the workflows to coordinate, it is almost certainly necessary.
GDPR does not prevent companies from storing personal details of their users/customers/etc for legitimate purposes. Instead it is intended to generate more thoughtful practices around the management lifecycle typically associated with this sensitive data.
For instance, what teams in companies do to record interactions with different flavors of users is track relevant and often personal details in whatever workflow tool the particular team happens to prefer. Maybe this is Salesforce, or JIRA, or email. Whatever.
This careless sprinkling of personal details around team-specific workflow infrastructure is one of the anti-practices a successful GDPR implementation will ideally deprecate.
So a deletion request management system needs store personal information that is used to match in other systems. It needs to be sufficient to identify the person requesting the deletion. That data can be retained for the duration of its legitimate need. When that need has expired- the deletion workflow is completed- this system is no different from any other. Personal details get deleted from the deletion request management system as well. (The exact policies and timing around this are of course decided by the legal team).
In terms of practices, the likely common practice with databases is scrubbing. IDs of records with scrubbed fields need to be retained, both for future validation and also to support the scrubbing process being applied following a restore of production data from backup.
When it comes to matching, one nit- my understanding as a non-lawyer is that what is considered to be personal information is not just identifying information like first and last name. Personal attributes that may not be identifying but are nevertheless unique and characterizing of a person are also subject to deletion/scrubbing.
Using hashes to efficiently match fields across systems may help, but with names, there are numerous spelling and other variations. Doing this sort of matching is its own data management practice that companies that have had to consolidate customer databases are likely familiar with.