I have recently aquired a small (30 user) domain structure, that was setup HORRIBLY. The previous IT Manager didn't know anything about best practices or the proper way of setting up DNS. Hell he hardly knew what DNS was!
Without going on a soapbox, I have come across an issue where various functions requiring domain access (Intranet site, Exchange, etc.) are at random times giving users a login prompt, and their accounts are not being authenticated. Even though the username and password are correct.
The only way to rectify the situation is to disable their account in AD and then re-enable it. After that it works fine.
Is this caused by something that I'm not doing correctly? Misconfiguration? Fluke?
Your event logs are trying to tell you what's going on. My gut says "name resolution problem" and that the enable/disable behaviour is just a red herring.
Try and get the "Default Domain Policy" and "Default Domain Controllers Policy" returned to stock settings after you document them. (Have a look at the DCGPOFIX utility.)
Look for other GPOs at the root of the domain or at the "Domain Controllers" OUs and investigate what they're doing. Disable them if they're not needed (but don't delete them until you're sure).
Verify that all the server and client computers have good DNS servers specified.
Did I mention looking at the event logs on the server computers where the authentication problems are happening and the domain controller(s)?
I disagree with "mh" on this one. You can probably get to the bottom of what's going on pretty quickly.
Any chance the users are getting locked out? Do you have the domain set to lock out after so many missed attempts? Perhaps you have a virus or rogue machine on the network authenticating as other users and locking out their accounts.
For that size of org it may actually be more cost and time effective to rip it up and start again. My instinct is that there are probably a lot more things wrong with it than just this credentials problem, any one of which could come back to bite you in the ass years down the line. Given the number of users you have, resolving them in your AD/DNS/Exchange/etc config could consume a lot more time than a simple rebuild done right would. And you'll come out of it with a known and rational setup rather than a patched up mess.