I don’t think this is a concern. With 14 alphanumeric characters in the record ID, and a current limit of 100,000 records per table, there is no need to reuse a record ID due to record count limits.
Airtable hasn’t published how they generate record IDs or whether they check for uniqueness with deleted records, but I wouldn’t be worried.
I suppose if you plan on creating and deleting hundreds of thousands of records every day, there might eventually be an issue. But if you are doing that, Airtable probably isn’t the right platform for that project.
If you need extra peace of mind regarding reuse of old record IDs, you could combine record IDs with record created time to ensure all IDs are unique including deleted ones. But this would probably be overkill.