Active Directory authentication rejected and the bad password count does not increment or reset

Do you have password history enabled? If the password entered matches either of the two last passwords for the account, the auth will be rejected but badPwdCount will not be incremented. I'm trying to wrap my head around the rest of your description, but that would at least explain the "missing" bad password increment.

EDIT

Rereading your question, it sounds like administratively resetting passwords always has positive results, correct? Also wondering what OS your PDCe is on (2003, 2008). Are there any firewalls potentially blocking access to the PDCe (or any other DCs for that matter)? Keep in mind that while end-user password changes communicated from the client to the local DC via the kpasswd protocol (TCP/464), PDCe notification of password changes are via an RPC call. The destination ports will have changed from 2003 to 2008.

This smells like a problem with either your replication or the DC that has the PDC Emulator role.

Can you run netdom query fsmo on each DC and compare the results from each? Make sure they all think the same server holds the PDC Emulator role. Next, take a look at the output of dcdiag and see what it has to say. Also, verify replication with repadmin /showrepl against each DC.

If I had to take a completely blind guess, I'd say that there's either an inconsistency in who the DCs think hold the PDC Emulator role, or the server that once held it was improperly decommissioned and the role was never moved.