No, it does not fail.
I tested this in my Alpha Sapphire. (I know this is for X or Y, but ORAS is the same generation, and Bulbapedia didn't mention any changes between the games.)
Regardless, I taught Thief to my Linoone, and went to Route 101. Linoone used Thief on a wild Wurmple and stole it's Pecha Berry, even though the Wurmple fainted. So, it doesn't matter if the wild Pokemon faints, Thief will still steal it's held item (if it has one).
You're probably getting very unlucky. Luvdisc only have a 50% chance to hold Heart Scales (as you mentioned). And surprisingly, Thief only has a 99.6% chance to steal the opponent's held item.
Also, here's the Bulbapedia page on Thief.