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.