After playing around with boot images, and the client package with all sorts of options to redistribute/validate. I started looking at my task sequences because they also consumed the boot images, and because I got myself into a position where smspxe.log started to show "no advertisements found" error, I stumbled upon this article that dealt with a similar issue: https://www.lieben.nu/liebensraum/2014/05/unknown-computer-support-and-multiple-boot-images/
In the end, the resolution was to just delete my task sequence deployment to "All unknown computers" and deploy it again. Hopefully this helps someone else out there.