Mad Cow,
How are you calling your logon script, directly from the users profile or thru a BATch file? Show us what you use.

How random is this? Random across all machines or just certain ones? Are there DCs that are not well connected or is this a small LAN?

If it were just XP, I would suspect Fast Logon Optimization but you claim 2K boxes also skip.
_________________________
Give a man a fish and he will be back for more. Slap him with a fish and he will go away forever.