I imagine as the starter solenoid is integral to the starter motor as a whole and will not function without, mechanics nowadays just fault out the latter as a unit, especially as it's likely the solenoid is no longer a service item. Would I be correct in thinking the "starter solenoid" that was found to be working ok was actually the remote starter relay? The reason I ask is that symptoms of your fault pointed so strongly to the starter solenoid.
For the sake of clarity as the terms are often confused, the definition of a solenoid is an electromagnetic mechanical actuator whereas an electrical relay is a solenoid that operates an electrical switch so there is a spill over. Further confusion lies in the case of the integral piggy back starter solenoid, as it functions as an actuator to engage starter pinion and as a high current switch at the end of it's travel to allow same to windings of starter motor itself.
In fact the solenoid itself has two windings one to provide main actuation and the second weaker winding to hold the engagement and switch for the duration of starter operation.
