New devices failing to PXE boot to SCCM because of existing ItemKey

We have a really basic SCCM setup, a single server primary site servicing 26 Windows Server 2012 servers and about 450 Windows 10 desktops.

We are experiencing a strange issue when PXE booting some devices (but not all) where a device that has never been PXE booted onto the network before tries to PXE boot and gets the following response in SMSPXE.log:

Request using architecture 9.   SMSPXE  02/09/2016 12:52:11 4076 (0x0FEC)
Client boot action reply: <ClientIDReply><Identification Unknown="0" ItemKey="16777850" ServerName=""><Machine><ClientID/><NetbiosName/></Machine></Identification><PXEBootAction LastPXEAdvertisementID="" LastPXEAdvertisementTime="" OfferID="" OfferIDTime="" PkgID="" PackageVersion="" PackagePath="" BootImageID="" Mandatory=""/></ClientIDReply>
SMSPXE  02/09/2016 12:52:11 4076 (0x0FEC)
Request retry.  SMSPXE  02/09/2016 12:52:11 4076 (0x0FEC)
Client boot action reply: <ClientIDReply><Identification Unknown="0" ItemKey="16777850" ServerName=""><Machine><ClientID/><NetbiosName/></Machine></Identification><PXEBootAction LastPXEAdvertisementID="" LastPXEAdvertisementTime="" OfferID="" OfferIDTime="" PkgID="" PackageVersion="" PackagePath="" BootImageID="" Mandatory=""/></ClientIDReply>
SMSPXE  02/09/2016 12:52:11 4076 (0x0FEC)
90:2B:34:77:96:EC, 03000200-0400-0500-0006-000700080009: no advertisements found    SMSPXE  02/09/2016 12:52:11 4076 (0x0FEC)

The way I read this is that the request is failing because the SCCM database already knows about the device and so it doesn't belong in "Unknown computers" and so doesn't have a PXE deployment targeted to it.

However, the ItemKey in the log snippet (16777850) is the Itemkey of a completely different device that has already successfully PXE booted and installed its OS and applications.

Reading around a little only yields a couple of workarounds and not a proper solution. The workaround that works for us is to delete the existing machine in SCCM that the new machine's request seems to be getting confused with, clearing the PXE deployments on the collection that the existing computer is in and then retrying.

9 times out of 10, this works okay but 1/10 it then hooks up the new computer with yet another existing ItemKey and computer and that one has to be removed too.

This is really quite baffling and I don't understand how a computer that SCCM has never seen before can already exist in its database yet be associated with a completely different computer.

I'd be extremely grateful if any of you SCCM gurus can point me in the right direction.

Cheers, Kevin.