Well, I finally found a solution, and I didn't have to run sysprep, or newsid or do anything that would interfere with the clients' membership to the domain. Nor did I have to physically visit any of the workstations to fix them. Here's what I did...
I found this article on Microsoft's support site: How to locate and clean Advanced Client Duplicate GUIDs in SMS 2003. It is an article that talks about upgrading from SMS 2.0 to SMS 3.0. We're upgrading from SMS 3.0 to ConfigMgr 2007 R2 so this shouldn't apply. However, I decided to give it a try anyway, and it worked! The article tells you to download the SMS 2003 Toolkit and copy a file called Tranguid.exe to the broken workstation. You open a command prompt, run tranguid.exe /R, then restart the SMS Agent Host service, and voila! New SMSID. It took a couple minutes for the ConfigMgr client to regenerate a new ID, but after about 5 minutes, I updated collection membership on the All Systems collection, and the workstation showed up installed and healthy.
So there's the fix. Now the next problem, how do I automate this on 250 PCs? Well first-of-all, I wrote a little batch file that would run the tranguid.exe command (I'm no scripting expert, I'm sure there's better ways to do this) and saved that to NewConfigMgrGUID.cmd. That looked like this:
net use B: \\ Domain\netlogon\scripts
B:
copy SMSCFG-bad.ini %systemroot%\SMSCFG.ini /Y
tranguid.exe /R
net stop "SMS Agent Host"
ping 127.0.0.1 -n 60 >nul
net start "SMS Agent Host"
c:
net use B: /delete
Couple of notes about this script: I put tranguid.exe in a folder called "scripts" in the domain netlogon share along side a known bad SMSCFG.ini file. I noticed that depending on how bad the client install was, the transguid.exe may or may not have been able to fix the SMSID. So I got around that potential error by overwriting the existing SMSCFG.ini file with a file that I knew would be able to be fixed properly (line 3). Also, I noticed that the SMS Agent Host service took a long time to stop and the script would fail because it would not wait long enough for the service to finish stopping. So I added the ping command in there to put in a delay of about 60 seconds before attempting to start the service again (line 6). This script will do the job...if you happened to be logged in locallly to the workstation with admin rights. Close...but not quite. I want it to be fully automated.
So next I downloaded PsTools and tried executing the script above remotely using PsExec. It worked, but the catch there is...the script above needs to be located on the workstation itself. So I wrote another script that would first copy the script above to the workstation, then execute it remotely. That script looked like this:
net use B: \\ Workstation1\c$\winnt
copy NewConfigMgrGUID.cmd B:\NewConfigMgrGUID.cmd
psexec.exe \\ Workstation1 -w C:\WINNT -u domain\user -p password NewConfigMgrGUID.cmd
net use B: /delete
(The psexec command is all on one line. This script is 4 lines total.)
I saved this script to FixClients.bat at the root of my C: drive. So then I put psexec.exe and the script above (NewConfigMgrGUID.cmd) at the root of my C: drive and executed FixClients.bat. What you end up with is a local script (FixClients.bat) running a remote script (NewConfigMgrGUID.cmd) all in the same command prompt (weird). This was a lifesaver due to the necessary pause needed between stopping and starting the SMS Agent Host service.
So all that was left to do was to run a query on ConfigMgr of all the PCs who did not have a client installed and export them to a csv file. A little Excel magic helped me generate a 908 line "FixClients.bat" file. (The same 4 lines above repeated for each workstation with the workstation name listed in lines 1 and 3). The gi-normous FixClients.bat file ran for a little over 5 hours. Beats the hell out of syspreping 250+ workstations spread out all across the county!