I think you covered the biggest ones already.
Almost all fairy tales begin with family problems, so fairy tale backgrounds of missing parents or mysterious parentage are very common.
Also common in myth and fairy tales are strange and powerful mentors or teachers, and so again you see a lot of those. It's also very common (and convenient) for replacement PC mid-campaign to be protege's or minions of some important introduced NPC. If there isn't a specific mentor, then the player often wants to have been inducted into a secret society of some sort.
If you don't see a mysterious or powerful mentor, then almost invariably they have some sort of feral childhood where they did on their own.
If the circumstances of birth aren't unusual, then it's often usual to have parents or mentors murdered and so the character has a motive for revenge. More rarely, but still fairly common, some relative is still alive or in need of redemption or rescue, and so the motive is rescue or redeem the family member.
There are also quite a lot of characters who have a criminal past, and are either now released from prison or bondage or else are fleeing to keep their past from catching up to them. In some cases, when the player wants a noble but tormented character, then the character will have escaped from kidnapping or slavery.
Often the character has escaped from some sort of near death experience or disaster. If this was a widespread disaster, they are often the sole survivor.
As you mention, visitations by the deity and personal callings to serve are common for divine classes like clerics and paladins. It's been a while but I've also seen "child of prophesy" backgrounds where the player hints at some story arc they want to be involved in.
It's very common for fighter classed individuals to have some mundane profession like caravan guard, sailor, or member of the city watch just prior to beginning the adventuring career. It's also fairly common to have "third son of a minor noble that has inherited only a family sword and is out to seek their fortune" as background. Bonus points if the noble family is cursed, disgraced, exiled, or otherwise down on their luck.
One thing in the thread I haven't seen but I think is really cool is "Running away from a forced marriage." Good concept.