Crashed services would also prevent users from using e-mail correct? We aren't having any issues sending and receiving emails.
I have narrowed it down to a server problem I think though. I reinstalled XP on the computer and still can't create a mail profile. I tried a second computer and am getting the same errors.
I see nothing in the server event log, so I kinda suspect an mail service has hung, despite still being able to send/receive e-mails.