Has anyone ever actually gone out of their way to spend any period of time playing against Halfbloods and come away feeling like it was time well spent?
I did it to kill time once back when I was a newb - I didn't exactly feel that it was rewarding, but I did get a few upped cards so I was content.
Is there any reason to have Halfbloods in their current format at all?
No. There's simply no unique purpose in the game's meta of opponents:
AI0-2 Are tutorial/practice/'fun' opponents.
AI3 - First-time grind, medium challenge, great for score grinding.
Arena - Variable challenges (even split into 4 different levels), easiest way to get rares and only way to get shards.
FGs - Crazy challenges for the first-time newb, an electrum grind for the expierienced player.
Half Bloods are somewhere in between Arena and FG purposes and don't do it as well as either.
If we were to replace them, what would we replace them with?
We shouldn't, IMHO. We should give them unique rewards that players would go for. Perhaps new rares, quests that focus on them, beating them unlocks new cards in the shop, or a set of "Uncommons" that only they wield. Since they've proven to be somewhat tough due to their unpredictability their rewards should be worth fighting them.
If they had to be changed, I would leave in the random card selection somehow. It seems to just be a trait that they handle very well, but don't reward players well enough for defeating,