TM actually needs some extra room before it starts a back up. This is a computed value and may not be accurate. However, it will not normally delete anything from any back up if you later delete that file. It will try to delete parts of the back up that you still have on your drive. Otherwise, you would permanently lose that file/app. So, if it "thinks" you have deleted a very large number of files, it will simply
not delete them from the last remaining back up that has those files. If that was the oldest back up stored, it could, possibly get confused about where to delete what?
Or, have you changed the name of your drive that is being backed up?
My opinion is that TM is absolutely great until it fails. I think it fails because it is so heavily dependent on the hard drive, accurate data transfer and real-time file size calculations. If it were just another app, you could always try to restore from a back up. But this
is a back up, so where do you restore it from?! Oops!
This is why most here recommend at least two forms of back up.
You are correct that it starts deleting the oldest back ups when it 'thinks' it needs more room. But if it gets confused as to how much room it needs, you may get the results you see. There are ways to manually delete old back ups, but I've never tried them. I've only had one malfunction like yours and I decided the risks and time weren't worth it since I had several back ups to optical media of the important files.
Some suggest altering the schedule of TM back ups and that may be of help to many. But I have had too many times where I was able to retrieve a file that had only been on the drive for a little more than an hour! In other words, if a file is not on your drive before a back up and you delete it, it will be lost for good! "Haste makes waste!"
<
Here is a link> to one of the best attempts I've seen at helping someone with a similar problem.
There are several links there to helpful apps, also.
Here are two different Time Machine FAQ lists that could also be helpful: <
TM FAQ> and <
TM Trouble-Shooting Guide>