Hi Josh,
Some VPN software can change the API call contents itself. I recommend using something like wireshark to see the changes your VPN is making to the call. Also the 404 should give you a reason for the rejection that might also be coming from the VPN or IP routing service itself and not even getting to Microsoft. Usually this is a firewall block imposed by the VPN software on Bing.com or VirtualEarth.net.
Note I can reproduce similar issues with NordVPN and their security turned on. Just try to calculate a route on Bing.com/maps with the VPN on and it will likely fail to find a route for the same reason.
Sincerely,
IoTGirl