A file with this name already exists... but it doesn't!

try this:
Check for Hidden Files:

Sometimes, files may not be visible due to view settings or filters. Ensure that your view settings in SharePoint display all items, including hidden ones.
Check if there are any filters applied to your view that might be hiding the file.
Search Thoroughly:

Use the SharePoint search feature to look for the file by name. This can sometimes reveal files that are not immediately visible in the directory structure.
Check File Name Restrictions:

Ensure that the file name does not contain restricted characters or patterns. SharePoint has specific rules about file naming, and violating these can sometimes lead to misleading error messages.
Verify Permissions:

Confirm that you have the necessary permissions to view all items in the library. Sometimes, a file might exist but is not visible to you due to permission settings.
Inspect the Recycle Bins:

You mentioned checking the recycle bins, but ensure to check both the site recycle bin and the site collection recycle bin. Sometimes, items in the site collection recycle bin are not visible at the site level.
Versioning Issues:

If versioning is enabled on your document library, there might be a conflict with an existing version of a file. Check the version history for similar files.
Clear Caches:

Clear your browser cache or try accessing SharePoint from a different browser or in incognito mode. Occasionally, caching issues can cause discrepancies in what is displayed.
Intermittent Issues:

Since you mentioned the issue is intermittent, it might be related to temporary service disruptions or bugs in SharePoint. Check the SharePoint service health dashboard for any reported issues.
Use SharePoint Designer or PowerShell:

Advanced users can use SharePoint Designer or PowerShell scripts to search and manage files in SharePoint. This can sometimes reveal files that are not visible through the standard web interface.
Contact Support:

If none of the above solutions work, consider reaching out to your IT department or Microsoft support for further assistance. They might have access to more detailed logs or tools to diagnose the issue.
Document the Issue:
Since the problem is intermittent, document the occurrences, including the exact time, the file name you tried to add, and any other relevant details. This documentation can be helpful for IT support to track down the issue.