Recently I had to reinstall my operating system and chose Windows 10. I had an issue with my NodeJS 3.x environment and switched to NodeJS 5.x. In doing so, I had issues with the node-gyp again.
It is not clear the order in which I installed everything or if the order matters, but I had to install both the "Visual Studio 2015 Community Edition" as well as the "Visual Studio C++ Build Tools". This was able to solve the various compilation issues I was having.