While we are waiting to upgrade the 3850 code to 16.3.8, we've implemented the "ip ospf lls disable" on the interface facing the Palo to see if the issue goes away. We'll remove the command a couple of days before the switch code upgrade to verify that the upgrade fixes the issue and I'll report back.
What's interesting is that we have not run the "ip ospf lls disable" on any of the other cisco switches that are facing Palo Altos in the environment and we don't see the adjacency going down. The site that is running 16.3.6 on the 3850s is the only location where we are seeing this issue.
According to a note from Cisco, "You may want to disable LLS on a per-interface basis depending on your network design. For example, disabling LLS on an interface that is connected to a non-Cisco device that may be noncompliant with RFC 2328 can prevent problems with the forming of Open Shortest Path First (OSPF) neighbors in the network."
If the Palo was noncompliant with RFC 2328, I would suspect that we'd see the adjacency going down at all our locations, rather than just this one site.
