Actually those are all true of OoT Ganondorf. The Gerudo are literally called a race of thieves by the other races of Hyrule and their ruler is known as the King of Thieves. Ganondorf's cruelty and ruthlessness can easily be chalked up to his elimination of the guardian of the Kokiri (The Great Deku Tree), the attempted starvation of the Goron's,the attempted murder on the patron deity of the Zora (Lord JabuJabu), and his plot to overthrow the King of Hyrule. Ganondorf was the King of the Gerudo and while not all of his subjects trusted him, his orders were followed by the majority. It is never stated that he is truly trusted by the King of Hyrule, only that the king shooed away Zelda's warnings that she got from her dreams. After confronted with the knowledge that Link brings with him from the future(the atrocities already committed by Ganondorf and the upcoming attack) it is easy to see that once the King confirmed the plights of the other races, that he was being told the truth by Link and Zelda and would have sided with them over a man who probably held a roll in the recent civil war. When he attacked Castle Town following Link's collection of the final spiritual stone, he laid siege to the town. It would be hard to believe that he did all of this single handedly before obtaining the Triforce of Power (As we see Zelda flee and a guard describe Ganondorf's attack before Link opens the Door of Time). Along with this Hyrule Historia definitively tells us that not only does TP come after OoT but that Ganondorf's execution was several years after the events of OoT.