How are you adding a record?
Running a script?
Go to a layout, select new record and start filling in the fields?
What do you do after adding a new record that reveals to you that an older record has been deleted?
That raises the possibility that some other action deleted the older records.
Try this test on a copy of your file.
Note the total number of records.
Add a record.
Check to see if the total number of records is now one greater.
If it is...
Close and re-open the file, perform other typical actions on your database and see if the number decreases back to the original number of records--you may have a script or relationship that is deleting records that you didn't expect to see deleted.
Sounds to me like you have a damaged file. Recover is useful, but it can't fix everything nor detect every problem. I'd replace this file with a back up copy if possible. If you can't find a backup copy of your file that doesn't show this problem, try saving a clone of your file and import the data into it. (This import will rebuild all indexes and this may fix the problem for you.)