Time Machine deletes older files if they have been deleted from the source when it needs space on the backup drive for a new incremental backup. Time Machine "thins" it's backups; hourly backups over 24 hours old, except the first of the day; those "daily" backups over 30 days old, except the first of the week. The weeklies are kept as long as there's room.
How long a backup file remains depends on how long it was on your Mac before you deleted it, assuming you do at least one backup per day. If it was there for at least 24 hours, it will be kept for at least a month. If it was there for at least a week, it will be kept as long as there's room. By default, Time Machine backs up hourly. That cannot be changed in Time Machine. There are third-party utilities that will modify the backup interval such as Time Machine Editor.
The Time Capsule sparse bundle grows in size as needed, but doesn't shrink. Thus, from the user's viewpoint of the Time Capsule, it appears that no space has been freed, although there may be space in the sparse bundle.
Once Time Machine finds it cannot free up enough space for a new backup it reports the disk is full. You can either erase the backup drive and start over or get a larger drive.
Your backup device is not large enough to hold your old backups plus the new ones started by your new startup drive. A Time Machine backup drive needs to be a minimum of 2-3 times the capacity of the source. Yours is not big enough to perform daily additive backups. You need to erase the backup drive and let Time Machine start over. Or use a different backup utility that overwrites old files with their newer ones doing intermediate backups. Another solution for Time Machine is to use a third-party utility to change the frequency of Time Machine backups. This doesn't fix the problem it simply reduces the number of regular backups thus extending the time between running out of space.
