myISAM data loss at DELETE / INSERT
Is it possible you've got two processes attempting to do this at almost the same time?  If this is a web application, could you have a site user who is double-click happy? 

Process #1 "examine existing users"
Process #1 "remove all users"
Process #2 "examine existing users" (no users would found)
Process #1 "insert new users and put existing users back"
Process #2 "remove all users"
Process #2 "insert new users and put existing users back (but no existing users were found)"