I was seeing this issue in a SharePoint 2016 environment (Event Log ID 8144 and ULS logs):
Failed to queue mysite for provisioning for user:[domain\user-DELETED-12066432-19B1-4F17-82C9-CF3FC9385325] with correlationid:[12066432-19b1-4f17-82c9-cf3fc9385325] on queue type:[Interactive]. Error:[Microsoft.SharePoint.SPException: The specified user domain\user-DELETED-12066432-19B1-4F17-82C9-CF3FC9385325 could not be found.
at Microsoft.SharePoint.SPWeb.EnsureUser(String logonName)
at Microsoft.Office.Server.UserProfiles.MySiteInstantiationManager.EnsureUserAndFixQuota(String owner, SPSite rootSite)
at Microsoft.Office.Server.UserProfiles.SiteInstantiationWorkItemJobDefinition.<>c__DisplayClass19.<AddWorkItemElev>b__18(SPWeb web)]
This error repeats every 5 minutes as the timer job tries to provision a MySite for this user, however it no longer exists (can happen in some edge case scenario’s mostly related to Active Directory).
Navigate to the User Profile overview, find the user profile and delete it to fix the issue.