since when they are deleted, you cannot look at their activity logs. Ask support, they can undelete them for you and might be able to tell you how they were deleted.
Are they non-existent in the database when you go back to add them? No record of them, etc? It's possible they've gotten blacklisted somehow.