At this point I would be checking the wiring to the starter FIRST and make sure a stray strand is not shorting. You may have say, melted / abraided insulation, and causing an intermittent.
Thanks for all the help, I appreciate anything you can give me at this point. Assuming there is nothing shorting or touching. Would it in the end be a starter issue, or starter relay issue? Could it be the relay? Could it be starter? It's been rocking this relay since before I bought the car back in say 2009. I've checked the wires, and none are touching nor have any strands showing. I'm guessing under dash wiring or some problem somewhere..