Just resolved an issue between us and a partner, along with Cisco TAC (us) and Palo Alto TAC (them).
Ended up being a mismatched PFS setting - we were 21, they were 20.
How could I have discovered this sooner, before having to invoke TAC assistance to figure out why we couldn't build more than a single SA at a time?