New Outlook 2003 profiles on Terminal Server 2003

Hi,

I had an Exchange issue which required me to recreate the information store.
The Exchange is on a Windows 2003 SBS SP1, and the recreation went without
event or any other reason to think it was not successful since then ...
except:

When this was done, terminal server Outlook 2003 SP2 users get a message
stating that "Outlook didn't shut down correctly... would they like to start
in safe mode?" This happens each time, without regard to the user's answers
on previous attempts.

I have logged onto the terminal server locally as a few of the users and
deleted their profiles. (I tired it remotely too.) I rebooted the terminal
server and created a new profile. However the same error occured.

I have uninstalled, rebooted, completed reinstalled and repatched to Outlook
2003 SP2, and the same error continues. From all my searches I take this to
mean that I was unable to remove the users mail profile, and recreate it
successfully. (I had to do this for some users who connect via Outlook on the
XP desktop computers, and it worked fine to get rid of a problem there after
the rebuild.)

How can I actually get rid of the old damaged profiles and create new ones
for the Outlook users on Windows 2003 (SP1) Terminal Server? (Or is my
problem something else?)

Thanks,
John