AAD Provisioning isn't built to expect deletion of users it manages from other sources - this is why you're seeing this problem. Ideally, you should be leaving management of these users, especially of deletions, up to Azure AD if it is managing creation/updates as well.
To break the links established between AAD and your connected target system, you'll need to restart the job via MS Graph API using this API call:
You'll need to use a body with a resetScope value of "Full" rather than the one provided in the example on that page. Be warned that this will break the links between all users in that provisioning job, and they will then be reconnected based upon current matching criteria set in the mappings for that provisioning job.