My other message is still held up in the moderation queue, I think (verified my additional e-mail before sending this), but you were exactly right. I neglected that we have a load balancer sitting in front of the directory server (2 replicas) for TLS termination reasons. I verified if I configured the load balancer to not round robin the requests everything works as expected -- it was just that it hit the other server to do the authentication with the new password before the change was replicated.
Thank you for taking the time to respond!