Sysprep on an already deployed system?

I've done some digging on the site and around, and I haven't seen anything that quite addresses my problem.

I have recently deployed a WSUS 3.0 SP2 hierarchy to a new data center and a pair of remote sites. Approximately half of the machines (almost entirely Win7) in one of the sites are reporting into WSUS but are showing no update status. That is the unique machine name is there, but no additional details.

Impacted machines have this error in their WindowsUpdate log:

WARNING: WU client failed Searching for update with error 0x8024400d

My research has lead me to belief the issue is related to duplicated Computer SIDS in one of the locations. It appears that a machine that was cloned was not properly sysprep'd prior to being imaged. I now have about thirty machines reporting the same SID (as determined by psGetSID).

In addition to rebuilding the clone image, I now have to resolve this issue on the thirty client machines. I am afraid they may have to be rebuilt.

1. I am aware that MS strongly states that sysprep is to be run on non-deployed machines. Can I run sysprep on an already deployed machine, and what are the ramifications?
2. Is there another solution the resolves this issue short of a complete rebuild?

You can't run Sysprep (or any SID-changing utility) on a domain-joined machine, but you should be able to remove it from the domain, run Sysprep on it and then join it back.