I have never encountered this problem before. This is my "shot in the dark" for you to try.
Let me recap your situation to see if I understand the problem:
1 domain
1 server running Windows Server 2003
8 workstations running WinXP SP3
40 domain user accounts
5 of these workstations that have no issues with any of the 40 domain users accessing the domain shares
3 of these workstations that have no issues with any of the 40 domain users accessing the domain shares the first time but not again until the workstation is rebooted
I would like to, for the sake of argument, name the workstations PC1, PC2, PC3, PC4, PC5, PC6, PC7 and PC8.
PC1 - no issues
PC2 - No issues
PC3 - no issues
PC4 - No issues
PC5 - no issues
PC6 - issues
PC7 - issues
PC8 - issues
PC1 - PC5 have no issues. PC6 - PC8 have the same issues. Since all 40 domain users can access all domain shares without issue on 5 of the workstations I am inclined to believe that this is not a user rights or privileges issue. I am more inclined to believe that this a computer account issue. We need to work with just one PC for now. Let us start with PC6 to try to resolve the issue and then apply the fix to PC7 and PC8, if I have the fix.
This is how I would approach this problem:
Backup any needed data on PC6
Make sure you have a local admin account on PC6 and can access it.
I would login as the domain admin on PC6 and delete any domain user accounts including the user accounts files on PC6. Make sure to remove the roaming profiles as well if you are using roaming profiles.
I would then join PC6 into a workgroup ( unjoin from the domain ) and reboot PC6
Check the server and delete the PC6 computer account, if it still exists
Login as the local admin on PC6
Change the Computer Name and reboot
Login as the local admin and rejoin the domain and reboot
Login as domain admin and set the domain users local computer rights and privileges
Map your shares and test access
Hopefully this will resolve your issue and you can apply this fix to the other two workstations. Should it not then an erase and reload may be your only option but it sure seems to be the computer account that is causing the problem.