Update stalls at "Checking for the latest updates for your computer" on nt4-style Domain

Hi all,

I have a smallish network (~20 workstations) on an NT4-style domain
(Samba 3 server on Ubuntu). Most computers are fine and all are running
WinXP Pro SP2 (most are on NTFS file systems). Some of the computers,
when running Windows Update, stall (I left one for almost an hour) at
"Checking for the latest updates for your computer..." and never
finish.

- I have disabled simple file sharing
- The domain user is in the local machine's Administrator group.
- All domain user's profiles are roaming profiles.
- When I disconnect the machine from the domain everything works fine.
- I can't install other programs, or use program that require admin
rights (ie: updateing Symantec Anti Virus Corporate Edition).
- I've renamed %windows%\SoftwareDistribution (in safe mode).

This looks like a permissions problem but I can't seem to figure out
why. I have checked permissions on various directories and none
restrict the Admin group...

I have tried reinstalling windows but the problem only goes away for
a period of time. I can't keep reinstalling the OS everytime this
happens, plus in some cases it happens right from the start.

Any help is appreciated!

Digimer

PS - I am little out of touch with Windows these days so please don't
hesitate to suggest "obvious" things