@Michelle:
Thanks for the additional info!
I wonder why they get automatically re-installed since they are optional updates. Is it a work computer that is affected by Group Policy settings?
I found this troubleshooting guide that might be worth trying otherwise: http://windows.microsoft.com/en-us/windows/troubleshoot-problems-removing-updates#1TC=windows-7