Cross-posting from another thread.....
Hrm. Maybe half-orcs could originate as humans who've been touched by the orcish deities, or orcs touched by the human deities?
Say, a human becomes the hero of an orcish tribe by chance, and the local shaman of Gruumsh blesses him in Gruumsh's name, making him an 'honorary orc' so to speak. The human is transformed and appears something like an orc, but still recognizably humanesque too. Ergo a half-orc.
As a half-orc, the blessed fellow can breed true with both humans and orcs, so his progeny would also be half-orcs (though after enough generations down the line, when breeding with pureblood humans or orcs, they'd just be orcs or humans as appropriate).
Similar situation: an orc orphan is adopted by humans, and the adoptive parents take him to be baptised in a church of Pelor. The holy water and baptism ceremony purges some of the orcish uglyness, savagery, and dull wits, granting the infant a more humanlike appearance and mentality, giving him at least a chance of being accepted into normal human society (and not just turning into a troublesome brute).