I understand where you're coming from, but it's too coincidental that the same problem is happening across so many machines, which leads me to believe it's something server level, affecting some but not all clients.
The problem persists though, even when the workstation next to a broken one is working fine. So surely that would indicate a workstation level problem rarther than a server one? As if the problem was intermittant, then a reboot half an hour later of a broken one would surely fix it?
Maybe im being daft here, but if the problem was with an intermittant server problem, then why would the affected workstations keep on erroring on every boot, whilst working ones work fine?
The last known configuration only works if the user doesn't logon. Boomam logged on locally, so the last known configuration wouldn't make any difference. As for the other two options, they may be worth exploring, but then again I disable System Restore by GPO as it isn't needed. Re-imaging would be more preferable when managing a number of machines.
Are these xp computers does last known config, safemode with networking get you on to the network? also does a sys restore allow you to reconnect to the domain, these steps may help you qualify that its a machine issue.