I think people underestimated elise because people didn't realize you could just put more cycle in your deck to hit your more important cards. Then the leftover cycle becomes legendary cards.
With Malchezar, I think you can justify more cycle the same way with elise, except you don't have to wait for the monkey to hit those higher value cards. I don't think it needs to be a super greedy deck, but it definitely fits the theme.
I don't think that discard lock was crazy for trying out malchezar, because when you're cycling your deck as fast as you can with that set up, it could be great pick ups. And if not, they just get cycled like any other card that isn't great in that situation. And it's not just the imp that cycles, it's also the 2 drop that discards + draws on death. And if you have 2 imps out, you draw twice for each discard. Discard lock could potentially be the fastest deck in terms of card velocity, perhaps even faster than auctioneer.
edit:
Another thing about the card, it's incredibly hard to play around. I've seen pros talk about playing around spells off of spellslinger... malchezzar is that times 5.
