There are two different ways to check the availability of Domain Names. DNS and Whois checks.

Whois Check

Whois checks make a request to the the Registry Whois Database to check if a Domain is available. The Whois check is the best way of checking 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 the Database contains over 30 million Deleted Domains. 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 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 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. This only affects a small percentage of Domains, but it can happen. 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 check. If the Whois check says the same, the Domain status on the website gets changed. This way the bulk checks happen using DNS, but the status shown on the website is the more reliable Whois 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 and the fact that between someone registering a Domain and the next DNS check can lay some time is why Domains are shown as available when they are not anymore.

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 special apis similar to the Whois checks 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 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.