I’m not sure why but it looks like this was an MTU issue. Both of my NSX Edge devices had an MTU of 1700 on their uplink while everything else in my environment is 8940. Not sure why this would cause the specific behavior I was seeing (only the first system to peer will receive advertised routes) but after reconfiguring the uplinks, all routes are received on both NSX Edge devices.
Thanks to all that chimed in to help me with troubleshooting this.
So the solution was to verify that VyOS and NSX agrees upon which MTU to use and in your case the fix was to change to 8940 at both sides to make it compatible with everything else in your environment?
Good catch! 
It would appear so, yes. I’m still not clear on how this would cause the behavior I was seeing though. I would think that with both devices having the same “bad” MTU, if it were a problem with BGP route advertisements, it would have failed for both, not flip-flopped back and forth. Regardless, lesson learned, and I’m glad it’s working as expected now.