How about introducing the option of queueing deployments? Queues will solve the VPN issue in a multi project/environment.

To prevent any misunderstandings, our environment is like this:

Project 1, 3 and 4 is deployed to servers hosted by our company.
Project 2 is deployed through VPN to a server hosted by another company.

The case we need to solve is to prevent failure when:
1) project 2 set up a VPN, and starts deploying.
2) project 1 initiates a deploy while project 2 is still running. This will fail project 1s deploy since the local environment is unavailable (until the VPN connection is closed).