It seems like I'm having to debug authentication-related problems several times a week, all with different symptoms and each with different errors in the Event Log. Today was the last straw.
I've decided to disable this poorly constructed component via Group Policy. Here's how I did it. I opened up Group Policy Management Console and created a new Group Policy Object.
Computer Configuration > Software Settings > Windows Settings > Security Settings > Local Policies > Security Options
Find the entry named "Network access: Do not allow storage of credentials or .NET Passports for network authentication". Enable this.
Assign the GPO to the appropriate OU and restrict using Security Groups as appropriate. I'm scratching my head wondering why I didn't do this a long time ago...