Lord nearly lost '02 and did lose '06. I'll defer to CT on whether that may be butterflied. Mike Harris: too old and can't win his province. Clement had already lost 2 leadership races and given how narrow his OTL win was, would have lost his seat ITTL.
He nearly lost in '03, and that was because of the issue of car insurance, if memory serves. Yes he lost in 2006, but he didn't lose the popular vote. I'm obviously biased because he was my Premier, but the guy was often touted despite his close call in 2003 and even since his defeat in 2006 he was touted as a possible MP at every election, especially in 2011.
The guy is far from perfect. He typically won't go for something unless his family is on his side (the reason he never went federal) or if it's closer to a sure thing. I honestly don't know if he'd go for the leadership. I don't think he'd go for the leadership in 2006 consider both the above criteria would be against him. He might wait a while on the sidelines like OTL.
The guy is still frequently mentioned as a leadership possibility, almost a decade after held elected office, and that says something. He's still only 49, plenty of time yet.
However if Lord wins in 2006, which is very much a possibility, then we're talking about an entirely different ball game.