The issue is that the SP's system time is several seconds before our IdP's system time, causing a failure on their side since the assertion IssueInstant (and thusly NotBefore) time is before their system time at the time the assertion is received.
This NotBefore time is not configurable on our side like the NotOnOrAfter time is - the NotBefore value contained in the assertion is exactly the same as the IssueInstant.
I mention adherence only because either our other (working) SPs have system times that happen to be after our system time, or they do not strictly adhere to the NotBefore value in the assertion.