Messages Queuing with Error 451 4.4.0 DNS Query Failed

on-prem Exchange server 2016 starts giving trouble for outgoing emails with the error message "Messages Queuing with Error 451 4.4.0 DNS Query Faile"

I need your support to understand the issue since we haven't found any issue with the DNS server since domain name resolution is working file and all other services are working fine.