SAML typically uses RSA-OAEP or RSA-PKCSv15 for KEM. You usually get the cert from that from the SP (since otherwise you hold the private key), so I'm not sure how that goes sideways. The SP might still use the same encryption keys for each peer, but that should be fine.

You're right that per-SP pairs are still the right answer and for the reason you point out: much wider support.