In my first game after retail, I had a 26 class planet sitting right next to my home star. After I terraformed it completely, I got it to a 36. Now, if I had hit the doubling event, it would have ended up being a 72... and a complete paradise.
It's possible, just very very very rare. When I got my 26, I mentioned it on the IRC channel and Brad commented that in all of the beta and gamma, he himself had never seen a 26 in one of his games. So if you see a planet that good, you're REALLY lucky to begin with.