Ok mortili is right it has to do with the amount of landmass, the game seems to generate a randomization of the ultimate quality of the tiles on a planet but the basic landmass is determined by the DDS file for that planet. It is possible to terraform every last tile on a planet but the generation system for planets seems to adhere to a lower limit of tile quality it will handle.
The issue you are seeing with terraforming is that each type of terraforming contains <LandPercentageMin>0.35</LandPercentageMin> this one is for the first terraforming tech.
Meanwhile this <LandPercentageMin>0</LandPercentageMin> is for the biosphere manipulator which is the penultimate terraforming tech and will essentially terraform any tile on any planet.
If you really really want a fully terraformed homeworld at game start just add this trigger to your AbilityDefs.xml
Select the ability you added it to, and your homeworld will start out with every tile terraformed at game start. Without actually needing to monkey with PlanetDefs.xml