The Windows Live thing is a likely culprit. ☹️ It's not something I've ever used... even when gaming in Windows. I wish there was a choice to install or not install that bit. The games do not "need" Windows Live to work properly.
I tried out the installer on the link provided, but that only works for Fallout 3 (which I don't have). It errors out and complains that I don't have Fallout 3 installed, and says I should install that game first and then try again.
I poked around in my Steam install and found two installs of Windows Live. I attempted to remove them using CXGames tools... but they wouldn't budge.
Interestingly... once this issue popped up with Bioshock 2 (at least I think it was with Bioshock 2) none of my other games would launch anymore - even ones that are known to work and were working previously. I ended up wiping out my Steam install and rebuilding the whole thing (and dummy me... I didn't think to make backups before deleting the Steam bottle...). No to do backups, and try again.