Some curious behavior I just noticed, our machines that have had the client pushed to them automatically upon discovery- do not install that client again once re-imaged. Manual push still works on tested machines so that ruled out admin account authentication, IP ranges etc. Someone suggested deleting the old entry from SCCM, and sure enough AD discovery brought the device back again the next day, but still no client.
I am 100% sure the solution lies in tuning Heartbeat discovery and the clear flag maintenance task. I have mine set up to run at weekly intervals and the CF task every Saturday, but yet here is Monday and the agent still hasn't deployed yet (but yet that "weekly" interval for Heartbeat discovery is vague so who knows what day it runs on- what log would this be by the way).