We have been getting the EXACT same issue, save for the fact that our environment is not set up using the Magic Triangle scheme (as far as I know)...
We have an AD server, but nearly all of our workstations are Macs.
We set up each mac by cloning a known-working clone containing only an admin account.
We then bind the cloned mac to our AD server, choosing the option to create mobile accounts, and then login with the user's AD credentials to create the mobile account.
As you described, the user is able to work on the machine normally for a few days, and then out of the blue I get a report that the password is no longer being accepted; not at the login page, the unlock-from-sleep page, or the unlock-the-padlock prompts.
One thing we HAVE noticed is that as soon as we remove the AD network connection from the equation, the user can log in with his/her password every time. This seems to make sense given other reports of being able to log in immediately following a restart: if you're fast enough, you might get the attempt in before the Airport card has a chance to use cached login info to connect to your wireless network. Similarly, if you're not using wireless and are instead connected via ethernet, logging in fast enough means you get your attempt in before the "network accounts unavailable" message turns to "network accounts available" (that issue has been reported basically everywhere on the web). What this suggests to me is that the cached AD user object information is correct, but the connection to the AD server is 'different' in some way than when it was originally set up. Given that we have people switching between wireless and wired connections at whim around here, I have to wonder if this could be a DNS-related problem.
The login issue described above has happened on about 5 computers out of about 100 in the past few months, and we've tried numerous online suggestions with no success. It only seems to affect machines running OS X 10.6 (we have several 10.7 machines that have had no issues after updating to 10.7.3, and never had this particular issue).
Some things we've tried without success:
1) Unbind/rebind computer to AD
2) Removing (backed up first!) the /var/db/dslocal/nodes/Default/users/username.plist file for the affected user and restarting
3) Altering nodes within the above plist file (password-->input known correct password)
4) Compared AD attributes to their mapped OS X attributes (SysPrefs-->Accounts-->AdvOptions) to see that they match (as far as we can tell, they do).
5) Repair disk/disk permissions (lol...)
Ultimately, to keep things moving around here, we've been employing this workaround:
1) Unbind machine from AD, reboot
2) Delete problematic account, but leave home folder intact.
3) Rebind machine to AD, reboot
4) Login with user's credentials to create mobile account.
5) Migrate all deleted user folder files to newly-created user folder.
6) Modify permissions as necessary.
Obviously, this workaround is not 100%: it typically involves a little extra setup on the user's part (getting those ~/Library files & permissions just right can be very tedious...) Still, it's A workaround.
Furthermore...I have noticed that whenever I perform this workaround, inevitably I end up with ANOTHER user reporting the same issue in short order on a totally different machine. This also lends support to the idea that this is a DNS-related problem.
Any other thoughts/suggestions would be greatly appreciated. I'll bookmark this post so I can add any important nuggets.