Connection to Microsoft Exchange has been restored. - SBS 2003 and Outlook (any version running on any OS)

For the last few months every single one of our Outlook clients drop and reconnect to the Exchange server whilst Outlook is running repeatedly, every minute.  

The only thing logged is client-side within event viewer:
Connection to Microsoft Exchange has been restored.
Connection to Microsoft Exchange has been lost. Outlook will restore the connection when possible.

The disconnects happen almost exactly every 60 seconds give or take a second or two.  The reconnect is virtually instantaneous.  This goes on forever but doesn't often start until 1 to 3 minutes have passed upon initially starting Outlook.

There is nothing logged on the Exchange server that I can find.

This happens whether Outlook is running in "cached mode" or not.  However when clients are not running in cached mode their experience is improved in the sense that messages seem to send quicker however the disconnects are still occurring.  

I can ping the Exchange server with 0% loss while the connection is dropped and reconnected.  

I can duplicate this at home on any of my desktops.  I can duplicate this in the office if I connect directly to our public WiFi (straight to the router and before the server and switch).  In other words, I can duplicate it anywhere on anything.

Here's what I've done:

* Replaced the switch
* Replaced the ethernet cables
* replaced the router
* replaced both NIC's
* everything in this article:
http://blogs.technet.com/b/sbs/archive/2007/04/24/common-networking-issues-after-applying-windows-server-2003-sp2-on-sbs.aspx
* Moved the Exchange transaction logs to their own hard drive

I'm at my wits end on this one and for some strange reason feel it's going to boil down to some obscure DNS problem that I can't figure out.  Please help and I'll name my next child after you!

Here's a screeny of a client's eventvwr

Here's a screeny of Outlook's connection status tool: