starter relay issue
The starter relays can be carefully opened, inspected and bench tested. On a high vehicle the contacts can erode enough to become intermittent. I have also found small spiders make a home there, and place web between contacts.
I am the curious type, and have cleaned and adjusted contacts getting several more years of use.