Devices not getting Updates and the report saying "Intune Sync Older Than 5 Days"

Posting this here in case it may help somebody else.

I checked the affected devices and they were not syncing with Intune with the error "The Sync could not be initiated (0x80072f8f)".

After some googling I found out that the service "Device Management Wireless Application Protocol (WAP) Push message Routing Service" was involved in the process. 

Not 100% sure why, but after just restarting that service the Intune synchronization worked.