There are two different ways to check the availability of domain names. DNS and Whois/RDAP checks.
Whois/RDAP Check
Whois/RDAP checks make a request to the Whois/RDAP database to check if the domain is available.
This is the best option to check the availability, but the registries limit the number
of possible checks. Some registries only allow a couple of checks per day,
but most limit the number of checks to a couple per minute, but even if the registries would allow
one check per second it would not be enough to check all domains in the database every day.
Currently there are over 500 million deleted domains in the database.
A day has 86400 seconds, so you could only check 86400 domains per day.
That is why DNS checks are used for the bulk of the work.
DNS Check
A DNS check is the same as what your browser does when you enter a domain in the address bar. If you enter a domain that has a DNS record, you see the website it points to or if it does not have one, you get an error. The DNS system is build for significantly higher request rates than the Whois/RDAP servers. You can easily make millions of checks per day. However a DNS check can't reliably say if a domain is registered or not, because domains do not need to have a DNS record, so it happens that the DNS check does not find a DNS record and says the domain is available, when in fact it is not available. The other way around is not possible. If a domain has a DNS record it is always taken.
Availability Check for Deleted Domains
This in mind here is how the availability check for deleted domains works. All domains in the list will periodically be checked using a DNS check. If the previous check said the domain is available and the current one says it is not, the system makes a Whois/RDAP check. If the Whois/DRAP check says the same, the domain status on the website will be changed. This way the bulk checks happen using DNS, but the status shown on the website is the more reliable Whois/RDAP check. Remembering the previous passage, this only works if the newly registered domain has a DNS record. If someone registers a deleted domain and does not add a DNS record, it will not be affected by this check. This is why domains are shown as available when they are actually registered already.
What to do
You can use the links provided when clicking on the domain name, to make sure the domain you are interested in is still available. The registrars have a special API similar to the Whois/RDAP check that can say reliably if a domain is available or not. The status column in the deleted domains lists shows the result of the last Whois/RDAP check. The "only available Domains" filter is using the value in this column. The DNS status columns use the DNS check result to display the domain availability.