If the starter spins but just does not engage, then it is in the starter or flywheel, not in the starter relay. The solenoid is in the starter; perhaps you mean the starter relay on the firewall? That is not an issue if the starter spins, as the relay and its ground has to work for the starter to spin at all.
The way this works is that the starter relay applies 12v to the solenoid in the starter; the solenoid activates and moves a lever which 'throws' the gear into engagement with the flywheel and also closes a contact inside the starter that puts the juice to the main starter windings. So if the starter spins, the solenoid is basically working but something is wrong with the gear not moving far enough to engage the flywheel, the flywheel teeth are gone/ground down, or the one-way clutch in the Bendix gear is not holding.
It probably has nothing to do with this problem but clean up the battery ground to the engine and the battery cable to the starter just to eliminate anything there.