Going back to the original question, I think the answer is Mike would have turned out the same Kay or no Kay. He convinced himself killing Sol and McCluskey were not crimes, but acts needed to protect his family, mainly his father. He went to Sicily and found faux redemption in Appolllonia, but when they blew up her car he realized he was not going to get out so easily. When he comes home, he is the heir apparent, and when Vito apologizes about having to drag michael into all this and how there was not time to have the family go "legitimate" Mike promises him "We'll get there." And the sad part is he kind of believes it.

He sees the move to Vegas as the beginning of the road to legitimacy, but Michael's problem is that he was a control freak and completely power hungry. Once he had power, legitimate or otherwise, he would never let go of it. Thats why he could have divorced himself from the olive oil business, and gone fairly legit in the casino business and eventually completely legit in real estate, but he could not accept the usual setbacks one has in legitimate business and get himself out of it without resorting to murder. Accordingly he maintined control in the Comission when he didn't have to, and he had his feet firmly planted in both worlds.