Starting with SP4, the NetLogon service caches old passwords for trusts.
1. Create the first direction of a trust successfully.
2. Create the second direction of the trust successfully.
3. Delete the second direction of the trust.
4. Re-create the second direction of the trust with a different password.
The trust is successfully created.
NetLogon used the cached correct password to validate the relationship.
The workaround is to delete the trust from both sides of the relationship.