When you jumped the starter solenoid the ignition switch was in run position. "It fired right up". Wild guess.. just maybe the root fault is the ignition switch. Just to test try that again. Maybe the ignition switch is intermittently loosing connections in start position. Maybe the starter relay wasn't bad after all.
