Troubleshooting Azure DevOps deployment stuck at 'Queued' status

Recently one of our customer was trying to deploy to an VM environment using Azure DevOps and all of their deployments were getting stuck at Queued status. To their surprise, they had idle Azure DevOps agents to work on the jobs. After scratching head for couple of hours, the fix was not what I had expected...