To find the new entries, simply sort the tables by ID descending, the entries with the highest ID are the newest.
I understand that stuff needs to be deleted from the table, but imagine you have 500 rows, and you are inserting data into previously removed id's. Then instead of being able to look at the highest ID's as they are the newest, you will have to look through all id's and decide if id 10 needs to be deleted again. It seems to me that this would create more work.
Maybe explain why you need to do this in a little more detail. What does the table hold. Is this from a contact form, or what kind of data is being stored? If we understand more about what the table holds, and why it needs to be cleaned out so frequently, maybe we can help you find a better solution. Include table structures and such.
I understand that some things need to be done, that may seem really strange to those who are not the administrator of the database, but this seems really strange and seems like it would cause more work than needs to be.