I had a similar issue with Desert Planets earlier this year. Since the last major patch, 1.61, I did start seeing Desert Planets on random maps.
When I posted about the issue, a few people claimed that they have had random maps with Desert Planets prior to the patch so I assumed I was just very unlucky at the time.
Since patch 1.61 came out, I've had random maps with and without random Desert Planets. I've also seen one with a single City Planet, one with a single Geomagnetic Planet, and two with two Gas Giants. It MAY be that you're just getting unlucky, but I understand how frustrating it can be. All I can tell you is that the bigger the system, the higher the chance for special planets....also, more stars helps, but probably not more than 4-5 stars on the largest maps.
Sorry I can't offer a solution.
-Gill