In the Plane of Time B: Spawns (or is "freed") upon the death of Quarm.
In The Void (A-G): Zebuxoruk is the lone occupant of The Void and has quite a story to tell. His dialogue can be found here, as can our Seeds of Destruction Progression information.
In The Void (H) (static): Part of the Call of the Forsaken expansion, Zebuxoruk is again the lone occupant of The Void. (For all things related to Call of the Forsaken, check out this overview of the expansion.)
In The Void (H) (instanced): Part of the Call of the Forsaken event "The Journey Home" (see this quest entry for details about the group version and this quest entry for details about the raid version).