It is necessary to create a blank/dummy profile in FIMS with the same id as the profile that needs to be deleted.
For example if the profile that was not deleted has a ID of 5000, create a new profile in FIMS with that id 5000 and then delete this newly created profile.
The sync will send a new request to CRM to delete the profile with ID 5000.  This will successfully delete the desired profile in CRM.