1) Murloc/Rush : Less desirable in murloc then rush, but the point is the same, if you have a board of 3+ creatures and your forecasting a board clear, you can void terror any non-buff applying Murlocs or a few creatures. The buffs from blood imp/Murloc warleader/Stormwind champion/Etc are counted when absorbing creatures, so if you eat two creatures and have a blood imp on the board, your void terror will at least have 6 health and 5 damage. (And likely much more)
2) Control/Other : In other decks, the card has incredible synergy with power overwhelming, ancient watchers, death rattles (Harvest golem, Cairne blood hoof, Loot hoarder, etc) And, last but not least of all, Faceless manipulator. A ancient watcher + another creatures (I find myself often using a harvest golem) followed by a void terror and faceless manipulator next turn is incredibly difficult to deal with.
In fact the only thing that i can think of that can deal with that long term (Where talking 4 10/10+ void terrors over the course of a game) is either a mage with Polymorph/Vaporize/Pyroblast or a Priest (Mind control, Mass Dispell, Silences, Etc)
Most of the time if you do the combo (Two minions, Void terror, Faceless) Your opponent will be able to deal with one, and die to the next.