All machines are running XP Pro.
All machines that are in question are remote users.
ICS is disabled on all machines.
DNS suffix box is blank on all.