Electrical Gremlins......Conundrum

Depends on what relay. How many "push on" flag terminals does it have. "Stick cars" before they had clutch safety switches had to ground the relay and only had one "push on" terminal for the start wire. All automatic cars, and cars 70/ after with the clutch switch have two push on terminals. One gets start voltage from the key, the other goes to ground through the neutral safety switch or clutch switch.

Sounds like next step is at the starter. Examine the terminals closely before you remove it. Might be easy for the terminal / wire ends to be touching and jumper the batt terminal to the solenoid, even a "stray strand" of wire