You can have a solenoid that will still click, but doesn't have the full battery voltage getting to it (that is what a "clicky starter" is).
What the clicky starter fix does is take the power from the battery and send it directly to the solenoid (via a relay that is activated by the key switch). It takes the key switch out of the equation, as far as directly providing power to the solenoid.
Put a clicky starter fix on and see if that fixes the problem. Even if it doesn't, it is still good to have it on there.
For the battery terminal fix, you can either get the lead caps, or you can use a 3/4" to 1" long piece of 1/2" copper pipe (whatever the height of the battery post is), and cut it down the side and slip it over the battery post. I've fixed a lot of loose terminal connections using the copper pipe method.