Embora você peça respostas canônicas, a origem de uma palavra provavelmente deve começar com a etimologia em inglês.
Mud mid-14c - Meaning "lowest or worst of anything" is from 1580s.
Pure c.1300 - In reference to bloodlines, attested from late 15c (Pureblood (n.) is recorded from 1882.)
Embora se diga que "sangue puro" é registrado desde 1882, o uso da referência pura a linhagens é atestado a partir do final do século XV, cerca de 100 anos antes da etimologia da "lama".
De Os contos de Beedle, o bardo :
By the seventeenth century, any witch or wizard who chose to fraternise with Muggles became suspect, even an outcast in his or her own community. Among the many insults hurled at pro-Muggle witches and wizards (such fruity epithets as “Mudwallower”, “Dunglicker” and “Scumsucker” date from this period), was the charge of having weak or inferior magic.
Note que, neste ponto, Dumbledore não está falando sobre os bruxos nascidos com pais trouxas, então a palavra "sangue-ruim" provavelmente veio depois desse ponto. Sabemos de Ron que:
É duvidoso que, quando Ron diz que a maioria dos magos são "mestiços", ele literalmente signifique meio-bruxo e meio-trouxa, mas que a maioria tem sangue trouxa e sangue "puro". Evidências parecem apontar para isso ocorrendo recentemente, na minha opinião provavelmente seguindo ou correlacionando com a perseguição de bruxos da "vida real" por trouxas no final do século XVII. Isso se deve ao fato de que, como diz a nota de Dumbledore, bruxos e bruxas que simplesmente "escolheram se confraternizar com os trouxas" estavam sendo perseguidos por sua própria espécie até o início do século XVII. Parece improvável que neste momento bruxos / bruxas estivessem se casando com trouxas para não morrerem. Esses eventos também foram um provável catalisador para uma necessidade de bruxos / bruxas se casarem com os trouxas para se preservarem.Most wizards these days are half-blood anyway. If we hadn’t married Muggles we’d’ve died out.”
Provavelmente então, a origem da sangue-ruim ocorreu em algum momento próximo do final do século XVII.
Uma nota interessante: Ao fazer a pesquisa para esta questão, encontrei um livro "Gypsy Sorcery and Fortune Telling", de Charles Godfrey Leland, escrito em 1891, que usa "sangue de lama" em um sentido literal (sujeira misturada com sangue para criar "sangue de lama") para uma cerimônia cigana. Eu apenas pensei que os paralelos entre uma "feitiçaria" encheram o universo de Harry Potter e um livro sobre "feitiçaria e adivinhação" foram suficientes para merecer uma menção. Se quisermos levar este livro para "existente" dentro do universo de Harry Potter, talvez seja uma indicação da mais antiga gravação conhecida de "sangue de barro" no texto.