The Altar is purely gameplay mechanic, and the resurrection of a hero is at the same lore level as producing a hero, i.e. pure gameplay. The descriptions of these buildings are simple flavor texts made to "explain" the resurrection, but beyond Warcraft 3, they don't exist. The only exception is the Altar of Storms, which was used to produce ogre magi during the Second War, by Gul'dan.
As for resurrection in terms of lore, I found these types of resurrection in general:
The inherent ability of a certain being to be resurrected. Demons, for example, are bound to the Twisting Nether, and if "killed" outside that realm, their soul returns to the Nether and reforms them, making them eventually able to be "reborn". Another example are the Ancients, who reform in the Emerald Dream, Cenarius and Malorne being examples.
The use of magic to a bring a body back to life. Death knights, the Forsaken and other undead beings were raised using Shadow magic, and I suppose Fel magic can be used in the same way. The Light is also known to be able to raise fallen heroes, but I cannot think of an example at the moment. Kel'Thuzad was raised using a combination of Arcane and Shadow magic, at the elven Sunwell. Illidan was also raised using Fel magic, in Suramar.
Blizzard intervention. You mention Muradin, but although he "died" in Warcraft 3, he later returned in WoW without having actually died (and the cause wasn't Frostmourne, it was a crystal of ice thrown away from the blade's prison). Illidan is also another example (his first death, in Icecrown).
Note that a "hero" is not a lore class or term. Any being may be resurrected (for example a unit revived by the paladin ability).
Generally, a great amount of magic is required to revive a person, and much more is needed to revive a powerful being. The body or the soul of the being must also be present, of course.
