Just posted this in the Window 7 Netbook thread and it was only relevant for our laptops and netbooks over wireless, but I thought I would still share. We have luckily never had this issue on a PC, yet.
What we have found is that students (and staff) are impatient. They shutdown and close the laptop/netbook and hand them in before the device has finished shutting completely down.
We have told the schools to make sure that the devices are fully off but they never do so if this happens now, we just get them to pull the battery out of the device and try again.
Works everytime.
Another suggestion would be logging in as local admin and running the "Join a Domain or Workgroup" wizard. This has helped fix some Trust Relationship issues we have had. Might be worth a try.