I've never used a VPN to run Exodus (desktop or Android) and have never had issues trying to run it... are you in a country or using a phone company/ISP that is attempting to block cryptocurrency or something?
No, but I remember a while ago shapeshift servers (Exodus Wallet uses it to make exchanges) blocked access to it from UAE IP addresses, so since that time I'm using VPN continuously.
Whenever I try to open the wallet the VPN connection stops automatically, I tried to access the wallet without VPN, some coins synced but most of them didn't.
I can still extract the private key but what is happening is strange, I installed the latest version, checked the wallet and checked that the coins using block explore and still have problems with sync.
Other wallets synchronize without VPN and for the same coins.