I've been breeding bees for a while too, and I've never seen a pure Common-Common to Cultivated-Cultivated pairing produce a pure-bred Majestic. Or even a hybrid Majestic. What I HAVE seen produce Majestics are:
Common-Noble to Cultivated-Cultivated
Cultivated-Noble to Common-Cultivated
It has never taken me more than 5 generations to get a pure noble strain from a few sets of pure common and pure cultivated bees (that can take a while if there is rain though). I occassionally have trouble with getting multiple diligent bees instead of the noble I wanted, but that's not the same thing as getting a random Majestic.
As an example, in my latest run, I got 0 noble princesses and 1 pure noble drone from the first batch of 4 mutations. I saved the drone and ran a new set of pure commons and cultivateds. This time I got a hybrid noble princess and 1 pure noble drone. I put the noble princess in with the pure drone, while still running another batch of mutations. Got a hybrid princess and 1 pure noble drone from the non-mutating apiary and a pure drone from the mutation batch. Next generation I finally got a pure princess and a pure noble drone. At no point in that sequence did I get an "unexpected" Majestic. And that's with a pretty incredible series of bad luck. Normally I pick up a pure and hybrid from the first mutation batch and I'm good after the second generation.
My worst sequence was when after 2 generations, I still had zero hybrid nobles. I did have a bunch of pure noble drones though. I put one of those with a random hive bee and got a hybrid noble. Then put that hybrid with another of the pure noble drones a couple times and got the pure noble pair I wanted.