Why would I get this error intermittently? "The server was not found or was not accessible"

It's possible that the server is too busy to respond - are you using SQL Express or Workgroup Edition? Also, how many connections at a time does this server have? Is this error happening on all connections at a certain time, or do some connections get rejected while others succeed at the same time?

Also, if you do a "PING -t Servername" and watch it, does every ping come back, or are some lost? This can be an indicator of network interruptions that might also cause this error.

We had this because of too many firewalls: the further away the client (say HK or NY, we're in Switzerland) the more often it happened. London: rarely. Switzerland: never. It was explained to us (via our DB engineering and MS help) that the delays because of routers and firewalls sometimes upset Kerberos and/or related timings.

Fix: use the port in the connection string. This avoids the roundtrip to port 1434 to enumerate the instance. We already used FQDN.

Example: server.domain.tld\instance,port

YNNV of course, but it worked for us

I've seen this before when I was accessing a remote sever at another location. I suspected it was due to the router configuration between the two sites as it was, shall we say, cludgy. It is entirely possible you're getting it because of a network configuration or bad hardware, but I wouldn't jump to that conclusion until you exhausted a lot of other possibilities.