Note - I've actually already solved this, but I don't see any detailed write-ups online about this issue so I'll go ahead and ask the question and answer it myself.
I run a service that authenticates as SMTPRelayUser that started failing ADFS authentication about 95% of the time. Inexplicably, this user would very occasionally succeed in authenticating and send all the mail that had queued up over time. In the ADFS Event Viewer logs, I was seeing two errors -- Event 300 and Event 413. Event ID 300 offered up no useful information, but 413 notified me of a strange exception.
Microsoft.IdentityServer.Service.AccountPolicy.ADAccountLookupException: Exception of type 'Microsoft.IdentityServer.Service.AccountPolicy.ADAccountLookupException' was thrown.
What's going on?
I checked the replication of this account across domain controllers and could see no reason that this should be failing. I turned on ADFS Debug logging and tried to login again. This time I was rewarded with a very clear warning that proceeded the ADAccountLookupException in the ADFS Tracing Debug log.
Event ID 53: AccountLockoutPolicy.IsAccountThrottled: The system failed to read the bad password count for user [email protected].
After checking the badPwdCount AD attribute for SMTPRelayUser on the DC being favored by my ADFS farm, I saw that it was indeed not set.
At this point I remembered that I had enabled ADFS 2012 R2 Extranet Lockout Protection a while back and it coincided with the onset of the login issues. Apparently there is a bug in Extranet Lockout Protection feature that throws an exception if badPwdCount is unset. I disabled the Extranet Lockout Protection feature and the login worked perfectly.
So why then did my authentications work 5% of the time? The badPwdCount is not replicated across domain controllers. Each DC keeps its own count. Occasionally, ADFS would actually consult a DC that had a badPwdCount value set and succeed authentication.
The moral of the story is to be careful if you're using the Extranet Lockout Protection feature in ADFS. I myself have simply disabled it for the time being.