Daniel:

I believe the UDP port used by SQL Server (MSDE) might be blocked.  Are the problem machines running a software firewall?  This could be a 3rd party product or, if XP, Microsoft's Internet Connection...

Thank you Frank for posting the Sommarskog links.  20 minutes of Google-ing yielded nothing as informative or on target.

Regards,

John