Wowpedia describes Durotar as it is now, not as it was when the orcs settled there. It was never lush, and life there was always going to be a challenge, but not an impossible one. Daelin Proudmoore did wipe out a lot of the trees they had.
Decay is entropy, not necromancy. A subset of death energy in the same way that Spirit is a subset of life energy. Decay is about ashen flame, poison water, rust, toxic wind and tortured earth, where Necromancy is the transformation of the flesh and blood creatures on Azeroth.
Essentially the ‘spirit of decay’ interacts with elementals the same way the spirit of the wilds does, but forcefully and destructively rather then in harmony. Yes they are elements all their own, no that does not mean they are not vital to shamanism, you NEED spirit to communicate with the Elements. Orc shamans deal in life energy, this has been established since the first one of them began to sense that energy in the earth back during Rise of the Horde.
No he didn’t. Rehgar didn’t hear about Thrall or the orcs going to Kalimdor until after WC3.