What if my legal name happens to be Wesell Heroin?
"Free speech" is a fairly generic term where the boundaries vary between countries, but generally it means that but for carve-outs you can say and not say what you want. Carve outs generally include things like "commercial speech intended to mislead".
I'd also expect that in many places with reasonably robust free speech laws might require to not refuse listings because the lister is in some list of protected classes (e.g. gender, ethnicity, ...). But nowhere is "apparently actively committing crimes" a protected class.
The american law around this concerns whether there is a substantial legitimate government interest in overcoming the free speech rights. In your example I'd think the courts would find one for lying about the other companies number (but not for merely declining to give it). If the phonebook-gravedigging-company has a monopoly on phonebooks maybe a competition (in a lawful market) based one for refusing the other companies listing. But neither of those interests are applicable in the case of responding to DNS queries for criminal activities.
Quad9's position seems to be that even when the request they are responding to is openly asking for something illegal (i.e. "please tell me the IP address for hire-a-hitman.cn") and someone has gone and told them that "hire-a-hitman.cn" is in fact a site for hiring hitman and a court has ruled that they must stop directing people to it they should still be allowed to direct people within the courts jurisdiction to it so long as those people take very simple steps to avoid announcing they are within the courts jurisdiction.
Of course the actual crime at hand is copyright infringement - but none of their arguments rest on that.