Microsoft Office 2016 encountered an error during Setup

I have found a solution to the problem and it calls for you to go into the scheduled task and delete the Office folder in that and then try to install Office. Try this...

• I know this is a necro post but I wanted to add to the solution list for anyone else who continues to have this problem, even now in 2016.

I was having this same issue and tried every solution on this post without success.  It should be noted, my issue started after I attempted to unininstall a component of my existing Office 2013 installation.  Instead of launching the "change" dialog of the MS Office Setup, the system registered that event as a flat uninstall of Office Pro 2013.  From that point forward I was unable to reinstall Office 2013 Pro.  I had other Office 2013 apps installed (Visio and Project) so I even removed those hoping that would fix it but setup continued to fail.

At any rate, I ended up finding the solution myself, however I do not fully understand why it was an issue to begin with.  At any rate...

I first properly enabled verbose logging by following instructions found here (since the instructions contained within this post seemed to miss a few steps):  https://blogs.technet.microsoft.com/odsupport/2010/12/30/troubleshooting-office-installation-failures/

While looking at the logs I found my issue stemmed from the following command trying to be run:  

It was erroring trying to register a scheduled task but was complaining that the system could not find the path specified.  After tracking with procmon I verified the XML file used for this command was actually being created.  I then focused on the other path mentioned in that error:  "Microsoft\Office\OfficeTelemetryAgentLogOn".

This is the path the scheduled task would actually live at so I opened Task Scheduler and drilled down through the path.  I found my path ended at "Microsoft\Office" and there were 0 tasks here.  

Since this path was empty, I deleted the Office folder entirely from Task Scheduler and re-ran setup again.  This time it finished successfully!

I don't know why the simple fact that the Office folder existed within Task Scheduler prevented this from running but its removal fixed my issue.