For me, it seems like the starter relay failing is a function of sitting unused for a while. Maybe after you replace it and are satisfied you have found your problem, you could pry open the cover tangs of the old relay, and take a look-see at what is preventing it from operating properly. What have you got to lose at that point?
