Is it possible they simply disabled the component instead of removing? There is no way that I can see that if the components were fully removed, they would magically come back...and you're right, policies being applied wouldn't cause this either.
Either they didn't uninstall like they thought or they were somehow added back.
And as for the prompt, it may be version specific, were that ones that prompted on a different version from the ones that didn't. Any time NTP is removed a reboot is definitely needed.