Comment by ctippett
Once the private link was reestablished, could they not have tunneled out to the internet via another server acting as a sort of gateway?
Disclaimer: I'm not a network engineer so I may be misunderstanding the practicality and complexity of such a workaround.