Does anyone have any ideas about this behaviour ?

This won't help much, but we've got the same problem, only worse.  Ours can't find either of our internal DNS servers.  We actually get three messages:

(Warning 2012) SMTP could not connect to the DNS server '10.230.48.200'. The protocol used was 'UDP'. It may be down or inaccessible.
(Warning 2012) SMTP could not connect to the DNS server '10.230.48.199'. The protocol used was 'UDP'. It may be down or inaccessible.
(Error 2013) SMTP could not connect to any DNS server. Either none are configured, or all are down.

The ...200 server is especially worrisome, since it's on the same switch as the Exchange server, so there's definitely Layer 2 connectivity. Pings succeed, so there's no Layer 3 problem.   No errors or warnings appear in either DNS server's logs.  We can run for days with no problem, then these messages pop up, usually in groups of three, roughly once per hour.  Yesterday, for example, they popped up at:

3:30-4:21-4:21 (1st warning, 2nd, error)
4:46-5:33-5:33
5:47 (1st warning only)
6:50-6:51-6:51
7:50-7:51-7:51
9:09-9:10-9:10
10:30-10:31-10:31

and it's been quiet ever since.

I'll kick in another 500 points for the answer to this one, assuming there's a way to do that.

Yes, ok, it will be good to get to the bottom of this one.

I think I understand what's going on here; hopefully some real expert can comment.  I turned on the network monitor trace, and traced all traffic between the Exchange server and the first DNS server (10.230.48.200).  I had to wait for a couple of days, but eventually a 2012 error popped up.  In the 3 or 4 minutes preceding the error, the Exchange server issued 3 "Std Qry" requests for a FQDN that the DNS server never replied to.  I don't know if the server was busy (not likely), it couldn't get a resolution, or what, but in any event it never replied to Exchange (for THAT query.  It was replying for other queries -- typically instantaneously -- all along.).  I think Exchange decided to give up at that point and declared that ...200 was "down or inaccessible."  It changed its mind 3 minutes later, though, and issued a query for the 2nd DNS server by FQDN (why, I don't know, since it knows the IP; maybe it was looking for it in another role, e.g., DC or GC) and got an immediate reply.  I wasn't logging traffic to both DNS servers at the time, so I don't know if the same query was then issued to the 2nd server, but I'm modifying my netmon filter to watch both servers and will let you know what happens.

Bottom line: I think this is a normal situation, where the DNS query goes unanswered for whatever reason.  Exchange, rather than issuing a warning along the lines of "Unable to resolve domain x.y.z.com" or whatever, says the DNS server is down, and most likely goes on to try another DNS server.  I'll bet that inspecting the delivery queue would show that the message for x.y.z.com was queued for a while.  

Stay tuned.

I've pretty much confirmed my previous comment.  These messages should really say something along the lines of "No response received from DNS server a.b.c.d in X seconds, for a query for FQDN x.y.z." for each server queried, followed by something like "DNS unable to resolve FQDN x.y.z".  A more comprehensive trace shows Exchange trying the first DNS server, receiving no response, issuing the first 2012 Warning.  Then it tries the 2nd server, receives no response, and issues the 2nd 2012 Warning, followed by the 2013 Error.  The failed domains do appear in the server queue, so I imagine there's some retry interval that eventually expires and the process repeats until Exchange gives up and returns some kind of an undeliverable error to the sender.

I just don't have time to dig any deeper right now, so I'm going to call the basic problem solved.

Basically then these messages relate to mails that can't find the destination domain and time out ?  Then you'll see these messages sitting in the queue's........

Right.  On my server, for every DNS lookup that fails in this way, there is a queue entry for the failed domain sourced from the virtual SMTP server. Section 4.5.4 of RFC 2821 (the SMTP RFC) describes retry strategies generally, and says "Retries continue until the message is transmitted or the sender gives up; the give-up time generally needs to be at least 4-5 days."  The RFC also requires that DNS be used to resolve the FQDN, and goes on at some length about what to do if the lookup succeeds, but doesn't explicitly say what to do if the lookup fails.

So, I'm happy as far as Exchange mail delivery goes.  However, I'm not happy that the DNS server doesn't give SOME response.  If I use nslookup on the DNS server to try to resolve one of the failed domains (e.g., "verison.net" -- give it a try on your system) I receive a "*** <servename> can't find verison.net: Server failed" message.  "Server failed" sounds pretty serious, but the DNS event logs show nothing, and it is in fact one of the three valid responses from a DNS server (Authoritative, Non-Authoritative (cached data) and Server failed).  I don't know why a "server failed" response wasn't sent to Exchange.

Time to post a question in the DNS area.

I've found that if I remove the ISP DNS servers from the settings in default SMTP server, this then removes these two events from the event viewer.  It seems using the internal DNS is good enough.  Although I still getting the warning event here and there but the critical events are not logged anymore.