1. Why there is inconsistencies and different behavior? For some machines it does not ask for reboot and for some it does.

Yes, This is expected behavior for some machines.  At the startup we check for couple of services. If we find them running, we stop them and do a reboot before continuing uninstall.  This is specific to VDA 7.7 to 7.11 on Windows 10 and Windows 2012 R2 only. This change was made in last release to solve the following issue. 

• Uninstall times for VDA versions 7.7 to 7.11 running on Windows 2012 R2 or Windows 10 operating systems have been reduced.  Earlier it was taking more than 20 minutes to uninstall VDA. This caused some users to think that VDA Cleanup tool has stopped working, closing the tool in the middle of uninstall and leaving the machine in a bad state. 

2. Is there way to identify if VDA clean-up has to run again after its reboot? Is there scheduled task that runs behind this? 

Yes, there is a way. After the reboot, SCCM will check followings:
• If there is runonce registry key for VDACleanup. 
• If VDACleanupUtility.exe process is running.  
 

Citrix is not responsible for and does not endorse or accept any responsibility for the contents or your use of these third party Web sites. Citrix is providing these links to you only as a convenience, and the inclusion of any link does not imply endorsement by Citrix of the linked Web site. It is your responsibility to take precautions to ensure that whatever Web site you use is free of viruses or other harmful items.