The Spiteful Legion

The Spiteful Legionnaires are a mythical Tiefling legion, bred for war and as a living sacrifice to raise demons at a crucial time. Each legionnaire is marked at birth with a molten black stone on their chest, and each is unique. The mark is a specific sigil of a specific demon, and only the highest ranking would know anything about this. The same rumour has it that the Black Pope is looking escaped members of this legion to recruit them into the Anti-Papal Guard - a group of military that serves the Black Pope.  Only a handful has been recruited after the legion found out their destiny, escaping to other worlds, including Earth.
The exact numbers are unknown at present, and there is little presence of them on Earth, with the Black Pope being the only one who has any knowledge of how many are here. A few are rumoured to serve other groups, but in miniscule numbers, usually a handful at best. Many would serve again if they can break the pacts laid on them when born, especially since their own mothers are killed after they are born leading some to resent that act. Many of the Underworld deities & their servants actively seek one out, at least to study them and try to convert them.
The Christian churches are terrified of them, as they view such a number as a dangerous proposition. In this they have started hunt down members they hear about with the help of the Ulmist Inquisition, and kill them. This sometimes involves assassinating them if need be. Also, they have started to try to form a specialist unit of the Swiss Guard comprised of Aasimar marked in a similar way. The difference is the Aasimar are marked in a way that upon death a Celestial is granted passage to Earth to take the former's place.
On top of all this there are old stories told by some ancient peoples of a great war between the Heavens & Hells, that had this legion take part in. Many look to the Wars between Dragonkind, and their war with the Giants, as well as wars involving races like the Black Elves, the Yuan-Ti, and many many more. The Spiteful Legion was hired to fight by many of the darkest of souls to aid in their wars, promised wealth, souls, and mortals to breed with. This in part is the reason so many cultures throughout the world resent and outright hated Tieflings. It helps shed light, to a degree, as to why some blood-lines also have a tendency for Tieflings being born in every few generations.

Summary

The Spiteful Legion was created as a way for the demons of one of the Hells to gain influence on the Material Plane, and to hire Tieflings out as mercenaries. They were to be used as a means to allow demons to gain a foot hold in the Material Plane by using the bodies of the Tieflings to appear. Each Tiefling is marked by a specific demon that will use their 'host' to enter the world they are sent to, and cause maximum damage when released.
This was kept from the Tieflings, who inevitably found out leading to many escaping and/or rebelling. Most are now spread throughout he Material Plane or further, and is the basis for many stories of how the Tieflings were first found on many worlds.

Historical Basis

Certainly many ancient battles, and a few more recent, had been won when a force entered the fray from an unexpected quarter. In a few tales, these new combatants were described as appearing from nowhere & looking almost hellish in appearance. Some could be explained by relief forces for one side or the other, or by more mundane mercenaries from abroad. Yet there is always a chance the new fighters are from unexplained quarter, and disappear shortly after victory is achieved.

Spread

The myth is quite widespread throughout the world, especially in mainland Europe, the Middle East, and Asia. Some theorise this is caused by stories, myths, and legends spread down the Silk Road. Over time they may have been embellished in some way when translated into other languages. Certainly a few spells common in some form or another allows for portals to be opened to other dimensions or worlds, and a few are permanently open in out of the way places. This could mean that such groups like the Spiteful Legion could easily have come across from somewhere else.

Cultural Reception

The general public are terrified of such a myth. Nearly every community that has heard of this prays that such a legion does not exist. After all demonic humanoids attacking en mass, possibly in the pockets of an enemy, is a terrifying prospect. Even more so when a devil-child is born in the local area.