If the replacement starter cut relay fixes the problem, that would be perfect. If it doesn't, I suggest having a close look at the spade connector (S terminal) on the starter motor. Given the location, I recognize that 'close look' is going t be a problem. The fact that the starter circuit restores itself each time you disturb this connection suggests that it might be suspect. It is possible that the wire strands in the crimp on the female terminal have fractured or that the raised section on the female terminal that retains the female terminal on the male terminal has deformed resulting in a poor connection. It is also possible that there is an intermittent electrical connection between the exposed portion of the male terminal and the actual solenoid winding. Applying some electrically conducting grease to the spade terminal may help with the problem if the problem is at the spade terminal proper. Penetrox A and Ox-Gard are two conducting greases. Do not use dielectric grease because it is an insulator.
With luck its the starter cut relay and the problem will never re emerge.