Random starter trouble

First I`d verify battery is good with a load test.
You know your solonoid is hanging up,= probably bad.
When it happens, test the solonoid to see if it`s getting power with key in run position. It should not.
I think you`ll be looking at a new starter