How can Facebook verify my face if it should not have one?

Facebook does not need to store the deleted photos. All they need to do is to use the photos you uploaded to extract the biometric details to be able to recognise your face. That data is what they use to verify new photos.

This is all outlined in their privacy and security settings. You can turn the feature to collect facial biometric data off.

To determine if the account is authentic, Facebook looks at whether the photo is unique. -Wired

They simply need to see if the photo is in the system to decide whether to investigate you further. If you upload a photo used by another user, you may be trying to create a fake account. Facebook also tries to determine the location where the photo was taken and whatever other information AI could gather. All that can be done without any prior photos or other data from you.

As for whether they have your photos, Facebook says they will delete them within 90 days if you delete them.

Facebook said the photos are hashed and then deleted from its servers.

If you do decide to upload your photo for the test, it will be hashed, but the actual photo will be deleted.

The process is automated, including identifying suspicious activity and checking the photo.

You seemed to think the process was not automated in a comment, but Facebook says it is.