This whole scenerio defies all logic regarding a NSS and/or the relay!!
The ONLY engineered way the starter can get juice is if the relay grounds .
The only other way is if the middle wire on the relay (the one that goes to the starter solenoid small terminal)gets 12 volts.
If there's no wire on the ground (G) side of the relay, then that tells me the relay is continuosly grounded. Yet a new relay doesn't fix the problem!!
Something is REALLY strange.