For the last few days, connections originating behind my LAN's NAT have been having issues completing the TCP handshake (i.e. web pages only load after hitting F5 a few times, network applications sometimes timeout when starting, etc.). After a TCP connection is estabilished, everything works fine.
My network configuration is ~20 machines behind an EdgeOS router, which masquerades internal addresses to my ISP's PPPoE endpoint. No updates or configuration changes have been made recently (last 6 months at least). I've excluded NAT port exhaustion, memory exhaustion and my ISP doesn't run CGNAT. The issue presents both on Windows and Linux machines, which means the culprit is most probably the ISP.
The issue at hand is, how do I investigate and document such a problem on my side?