The default setting  for the Local Intranet zone  is to pass  credentials.
But that's only the default. Did you double check the security  settings
to make sure that the credentials  are actually being passed. It's the
last set  of 4 radio buttons in the security panel.

Also, is the XP box standalone or a member of the domain. If its
standalone it won't be passing the right credentials since it won't pass
the domain  name.

Every other machine on campus works. Yes the local intranet zone  is set
to pass  credentials.

The Strange part was though I navigate to publichost.domain.edu the
Login prompt looked something like this

--- --- --- ----

+ privatehost.domain.edu

--- --- --- ---

+

+

+ Login to publichost.domain.edu

+

+ [ publichost.domain.edu\accountname ]

+ [ Password ]

+

--- --- --- ---

The credentials  had to be changed to [ domain.edu\accountname ]

I'm interested in knowing how this client knew AT ALL about the internal
host name. I don't even have that host name in alternate access
mappings. I thought maybe that was the problem so I just added it in. I
haven't contacted the customer to see if that made any difference.

Go into the control panel user  accounts and advanced tab manage passwords.
Clear it and/or remove users profile..

I called the user  to try this and I never had to!

I think it started working as soon as I put privatehost.domain.edu in the
Alternate Access Mappings.

Why the server would respond with a authentication  challenge for this Host Name,
I don't know. It should have been the public, load balanced URL everything else
authenticates to.

And Yes I checked. The machine is a member of the domain.

I just got a report though that this department frequently has
authentication problems with sites  external to us too.

I wonder if it is a security  policy