I am running Windows XP Service Pack 2 on a total of 16 machines at
work. Each employee primarily uses their own computer, but as they log
on to the Domain, they have the ability to log on to any computer
company wide. On at least three machines (have not checked any
others), I have a problem where desktop settings are not being
preserved. One user arranges the icons on his desktop in a certain
fashion that works for him and they stay constant through restarts and
log on/off as long as no one else logs in to that computer. As soon as
a different user logs on and logs off, this user will log back on and
his desktop will be completely rearranged - even if the other user
changes nothing on their desktop.

Any idea how I can configure XP to preserve his desktop arrangement?

Get rid of roaming profiles and make local profiles for all users
(this will also ease your network traffic, further more move all the
settings from the All user area to each specific user , it is a lot of
work but if you are running a small shop it is feasible

Give them all their own profiles and log in names/passwords. That way,
they can do what they want with their desktop and it won't effect
anyone elses..