For me, it was a device that had fallen out of our main "Site" into "None", and as some of us may have discovered in the past, there is no way to search for devices that do not have a "Site" defined. You can add a search to a site, but you cannot search for which devices are in a Site. Our profiles were also added to the main site, and because the devices were not in there, they did not get the profile.
