Recovery mode behind corporate proxy Sierra
(I know the phone hotspot didn't work for you, but it worked for me, so I'm posting it as an answer for others' benefit.)

Background: Macs need to connect to the internet when installing macOS, even if you have a USB bootable installer. It needs to download info from apple.com. The problem is that it doesn't work when behind a proxy.

The workaround is to use your phone's wifi hotspot for the initial verification step. If you use a USB bootable installer, then it won't need to download the 5+ GB through your phone's wifi hotspot.


Create a USB bootable installer. https://support.apple.com/en-us/HT201372
Unplug any ethernet cables to your mac. Otherwise, even if you connect to your phone's wifi hotspot, it will use the ethernet adapter, which will fail in the corporate network.
Boot to the USB. Before you click on "Install macOS", choose the wifi network (your phone's hotspot).
Then continue the rest of the installation steps. If the wifi works, then you should see the License Agreement screen pretty quickly (less than 1 minute). If it's hanging more than 1 minute, it probably can't get through to the internet.


If you're using the USB bootable installer, you can turn off your phone hotspot after the install process has done a few reboots and is in the "Estimated time remaining..." phase.