CM12 SP1 CU3 The task sequence will not start for machines with previously failed required deployment

Recently we received a request for assistance, on the following ConfMgr 2012 SP1 CU3 issue:

When using OS-Deployment to unknown Computers >>> that  works as expected...
When using OS-Deployment, theTask sequence fails on some Computers with previously failed required deployment...  OS Deployment to these Computers will never start via LAN PXE boot with the message: “no advertisement found
 
Systems don't appear existing in CM12 console and there are no “unknown” Devices in DB.
The following query gives no results...
select SMS_R_UNKNOWNSYSTEM.ResourceID,SMS_R_UNKNOWNSYSTEM.ResourceType,SMS_R_UNKNOWNSYSTEM.Name,SMS_R_UNKNOWNSYSTEM.Name,SMS_R_UNKNOWNSYSTEM.Name from SMS_R_UnknownSystem where Decommissioned = "1"
 
In the SMSPXE.log you may see the following lines:
Getting boot action for unknown machine: item key: ########
####MACAddress#########: no advertisements found
 
######is Ressource ID x64 Unknown Computer

This is a "known issue" when deploying to Unknown computers with a required deployment. You have to “Clear the PXE Deployment” on the PC but there is not a way to do it directly. When you PXE boot that PC for the first time there is an “Unknown” object that gets created. Once that object exists it won’t PXE boot again until you clear the PXE deployment on it. There’s only one problem – the option to clear the PXE deployment on the object is greyed out, and also, if you deleted the Unknown object, it still doesn’t clear out the PXE deployment. There are two ways to handle this: 

1)      Add the Unknown object to a Collection, and then on the Collection choose the option to Clear the PXE Deployment.
2)      Delete the Unknown object, then manually import it using its MAC address or SMBIOS GUID. On the manually imported object you will then have the option to clear out the PXE Deployment.

In general:
This specific error occurs, when a machine is identified as an unknown computer, before the Import Computer Information is used.
For example: when you PXE boot a client without importing it to ConfMgr first, it is identified as an unknown computer. If you try to import it using the computer name and MAC address, this error is shown.
When the error is displayed when using the import computer information functionality, the computer is already known in ConfMgr as “Unknown”. The MAC address registered to this Unknown object corresponds to the MAC address you use to import a “new” machine. The machine is probably registered as unknown because of an earlier PXE boot. It seems correct for the ConfMgr to deny the import of the “new” client, and this error really means that an object with the same MAC address was already registered in ConfMgr.

So basically, it doesn't add a new record if the record with same MAC address already exists..