I've definitely run into this problem, and my answer is usually to build a deck specifically to force people to interact earlier. Usually, this means building some sort of terrible Sligh deck or suicide black deck. If you build these right, you'll almost always be able to kill at least one player before they do much to disrupt you, especially if everyone's focusing on cards that cost 4+ to start interacting with other players. Play either an aggressive suicide-sligh style of deck with
Sulfuric Vortex and
Flame Rift and stuff like that, or an aggressive, but fragile, combo deck.
D0su built a sweet mono black
Doomsday combo deck awhile ago. That style of deck is a BLAST. you just run all the "draw some cards, lose some life" effects, some marginal beaters and whatnot, and just try to crush people as quickly as possible. It'd make Malfegor a little better, at least, since you'd have more cards, and it'd give you an impetus to win quickly.
If you're willing to consider mono-colored decks, I think you get a number of cool options.
Zo-zu and Adamaro make sweet sligh generals. Zo-zu + Grafted Exoskeleton is some kind of disruption. Both would be built to drop their general on turn 1 or 2 as frequently as possible, back it up with some 1cc disruption like
Crack the Earth and
Tremble, and you've probably got a deck that will warp the metagame pretty harshly.
In mono-black, you've got the Doomsday suicide combo, and you can also run Maralen suicide combo. Just run Maralen, 80 some swamps, Ad Nauseam, and some combo finish. That'd be a pretty cheap way to beat people into doing stuff.
The problem with each of these plans is that they'll just encourage people to run cheap counters and spot removal, which is fine if it's in place of wraths and stuff, but isn't as good if they cut actual win conditions.
The other problem with these decks is that people hate them so much. Games are boring when everyone thinks they can play control, but no one likes when you apply the pressure, and you'l frequently get hated off the table so fast your head will spin. It's the kind of deck that I pull out once or twice every couple of weekends just to keep people honest.
I really do think, though, that some mono-colored deck that forces interaction is the way to go. As soon as you start playing Malfegor and other high cc cards, you're not really playing a beatdown/pressure/tempo deck, you're hellbent-themed control deck.