we have noticed in our enviroment that safeboot is very sensitve to incorrect date and time stamps and with our large base of mobile workers this has resulted in a lot of account corruptions both on the server and the local device.
We have got around this by making sure our SB server sync with the NTP server then setting the client device to sync thier date and time with the server (the option can be set under the device properties tab in the managment console)
I know this dosnt show you how the account got removed but it most likely hasnt its jsut corrupt. so clear the machine audit, recreate the users token and turn on the time settings and you should see the problem go away. hope this helps