1) A private frame relay network that one day stopped passing packets over a certain size. Worked around by lowering the MTU at both ends till I was able to convince the frame relay provider that yes, the problem was in their network. This was relatively straight-forward to diagnose, but it was still odd being able to ssh into a box, then have the connection hang once I did something that sent a full-size packet (cat a large file, ls -l in a big directory, etc).
2) A paging gateway program I wrote (email to SMS) that worked fine when testing on my Mac, but couldn't establish connections to a particular Verizon web site when I ran it from a Linux box. Turned out that the Linux TCP stack had ECN enabled and at the time the Verizon website was behind a buggy firewall that blocked any packets with ECN bits set.
3) A Solaris box that could randomly be connected to, but not always. Turned out someone had deleted its own MAC address from its ARP table (yes, you can do this with Solaris) so it wasn't replying to ARP packets for itself. As I recall, it could make outbound connections, and then you could connect to it from that same peer until the peer timed out the ARP entry. Then the peer couldn't reach the Solaris box again.
None of these are nearly as complex as the scenario in this story.