Benjamin,

how did the broom stick work?

Our '87 used to do the same when the weather was hot or after driving at high speeds.
Replacing the solenoid did not solve the problem. An additional wire connected to the 'hot' side of the solenoid terminal showed that under those conditions the battery would only supply 8.5V to the solenoid - not enough to engage. Following the wires and determining the cause of the drop revealed 'a little every where': some connectors, key switch, long wires to back etc. Cleaning and replacing some connectors made it work for a while, but the problem re-appeared.
Since I had the wire still connected I would touch the pos terminal of the battery with that wire and it starts right up. I don't recommend this, but it worked for our trip - back home I doubled up some wires.

To identify a problem like this, hook up a meter and see if you get enough Voltage (>10V) to the solenoid when you turn the key.

just a thought.
Wolfgang Ziegler

79 convert.
88 GL
00 Jetta