Blake, I get somewhat simular problems, but only from my WinXP box. If I cannot access a site from my XP machine I can go to my Win98SE box and access it with no problem.
It also includes checking mail from my XP box too.
Sometimes if I reboot the XP box I can browse and check e-mail, but it is not consistent.
I was thinking I had a problem with the XP box, but reading through this thread causes me to belive it is a problem in SME 5.1.2 since my problems began immediately after upgrading my server from 5.0 patch 3.
I haven't had time to do a detailed check of my system, but I should get around to it this week I hope.
Tom