Error “Setup cannot continue. The Microsoft Runtime DLL installer failed to complete installation.” VMware tools setup

Came across a strange one today. Got the error message in the title. A bit of further digging revealed that the windows installer service would not start with Error 14007: The requested lookup key...