1: As you noted this is strictly a timing issue. The desktop is probably logging off, syncing profile, and then going through the process of deleting. Perhaps these all processes that need to be complete before the user's session is lifted and they can get a new desktop.
2: Did you note if maybe they are getting connected into the same desktop that was rebuilt?