Thank you for posting this concern on this community.
I just wanted to double check if the following details were reviewed as shown down below:
-Did you check for any asymmetric routing path issue?
-How is your routing set up on your NVA (Network virtual appliance)?
-Do you have just one internet provider or dual internet provider?
-How did you set up your NAT on your NVA?
-Did you configure any VM behind the firewall and check internet connectivity?
Looking forward to hearing from you
Please "Accept the answer" if the information helped you. This will help us and others in the community as well.