I once had much the same problem and went through many of the same diagnostic processes, until finally (with the help of the cable TV service tech) we found that I had slightly moved my computer hutch, just enough to damage the co-ax cable where it plugged into the wall.

Since in your case power cycling the router fixes the problem, that probably isn't the answer, but it couldn't hurt to check.

tanstaafl.