I guess you'd be thinking of Ted Stevens as the notorious one exception, but he hasn't really been gone for a while, he's only been gone since last year.

While Ted Stevens occupied one of Alaska's seat, two other Senators (Mike Gravel, then Frank Murkowski) served multiple terms each since the 60s. Murkowski was re-elected in 1986, 1992, and 1998, before resigning his seat after being elected Governor in 2002. Before him, Mike Gravel got re-elected in the 70s.