Interstate is a pretty solid battery. Pretty much all the ones that you'll find are going to be made by Johnson Control Battery- that includes Interstate, Diehard, Optima, Exide, etc. I'm pretty sure we discussed this at length before.
As far as the longest lasting battery I had in a car, it was ~7 years, Gates battery (late 80s, early 90s). They don't make them any more - Johnson Control Battery Group bought up the Gates SLI group (they used to make the Optima batteries and Champion Gel batteries).
Worst battery I had - Diehard, lasted 2 years - got it replaced under warranty, the second one died after 8 months. That was the time you only got one replacement under warranty, then it was prorated at that point. Switched to Interstate after that - battery lasted about 5 years, until the car was totaled in an accident.