[swl]

Tracking down intermittents is such a PITA. When it fails to start does it fail enough that you can use a meter to track the path? Or is it the sort of thing where one key turn fails and the next succeeds? If you can get some time in fail mode then a volt meter can help. Other than the switch there are only two terminal connections on the way back. You should be able to isolate it by checking for 12 volts coming into the relay board and then leaving the board.

With all that you have replaced there really isn't much left other than the wiring harness and connectors. I suppose you could run a direct wire from the switch to the relay or even the solenoid to test the harness theory. I wouldn't leave it that way though because it would be an undocumented obstacle during engine removal.