How to fix “we couldn’t connect to remote PC because the PC can’t be found” error in Mac (ZScaler + Microsoft Remote Desktop)

I was using Zscaler and Microsoft Remote Desktop to connect few remote VDI (Virtual Desktop Infrastructures), and everything was working fine before. However, I got an ugly error like one above one day.