Exchange: Email error 451 4.4.0 DNS query failed

After an upgrade of DC¬†to 2012R2 and removing the old 2003 DC I found that Exchange had problems sending mail to a small amount of different domains. When I looked in the message¬†queue I found that all these domains had the same error: domain.com 451 4.4.0 DNS Query Failed Since I just had installed two…