Sounds like an ARP issue to me, as a policy installation will force a gratuitous ARP for all firewall and NAT addresses if the cluster object is not set to use VMAC (which is the default behavior). Next time you have an outage, check the ARP caches of the surrounding routers, are they losing the IP to MAC mapping for the firewall and/or NAT addresses? Command fw ctl arp might be helpful to diagnose. If it is found to be an ARP issue, you can try setting VMAC on the cluster, reinstall policy twice and see if it helps.
Gateway Performance Optimization R81.20 Course
now available at maxpowerfirewalls.com