Permanently Deleted Contact Records Keep Reappearing
Are those real contacts? Can you check the created date against the contact? It shows up at the bottom when you view the contact or you can grab from civicrm_contact.created_date using mysql.
If the dates are changing than it means those contact are created via Bots. Could check all the forms which are accessible to anonymous user have recaptcha installed these includes user registration, membership signup or event registration etc? Include recaptcha on all your Civi profile forms. Visit the permission page to check if anonymous user is allowed to create contact.