Here's one that stands out from my previous career in cellular telecom.

The story goes along the lines of, our engineering team purchased a vendor supported BIND solution, to replace our unmaintained linux bind servers. Sometime after that, our GRX provider (one of the companies that connect various cellular networks together), had one of their DNS servers down for replacement, and an outage on 1 of 2 working DNS servers. Our problem was, we didn't failover to the last working server, and all inbound roaming (users from other countries coming to Canada) was down (cached stuff still worked until the caches started expiring)

In cellular roaming for IP services (circuit switched voice works differently), the routing per APN back to the home network is done using DNS. However, in investigating this and similar problems, I eventually found that this wasn't fully standards compliant. And even when talking to our DNS vendor about this problem, it was difficult because they weren't familiar with the quirks of the GSMA recommendations.

The outage was eventually recovered, but the question remained why did it happen?

This took place over a 2 or 3 weeks period, and I don't remember the exact sequence of events, conference calls, etc now that it's been several years. But I do know I ended up building a simulation of 3 networks (My Own, the GRX Provider, and a roaming partners network). Using dig to datafill each server with the exact response from the partner. This allowed me to control the startup / failure of each server across the simulation of the 3 companies.

Using this simulation I eventually found the root cause.

When BIND started, it would take our root hints, load them into it's cache, and begin to perform AAAA queries for the root servers. One of the upstream servers would respond with 0 records, the other would respond with NXDOMAIN. The server that responded with NXDOMAIN, would subsequently get deleted from our BIND servers cache, and would no longer be used as a root.

The next question was why?

After some sleuthing through the DNS RFCs, I eventually found the answer. There are two ways for a DNS server to return that an answer to a query doesn't exist. Returning 0 records, and returning NXDOMAIN, and they have slightly different meaning. Returning 0 records, means that the label (think example.cm) exists, but the type of record does not (AAAA doesn't exist, but A/SRV/TXT/etc might). Returning NXDOMAIN means the the label doesn't exists, for any type of record, so don't bother querying me again for a different record type (There may have been some vagueness around this, I don't remember).

The second discovery, is that we had a typo in our configuration, what we configured as the name of that root server, didn't match what our GRX provider had configured, which is why we were getting NXDOMAIN on one but not all servers we had configured as our roots.

The next question was why were our old servers working? This typo was actually duplicated from our older servers... which still worked during that outage.

So using my simulation, I tested every version of BIND released across something like a 3 year period, until I found it. Older version of BIND interpreted NXDOMAIN the same as 0 record answer, and at some point, I can only assume they fixed a bug, that updated this interpretation of NXDOMAIN.

Yay for not finding out you're redundancy doesn't work, until it's actually triggered.

Anyway's, there were many challenging issues like this in my telco days. This probably isn't close to the hardest, but hopefully made sense to those who don't have a background in telco standards.