I second both the consort / queen idea and the world war idea. The elves have long had reason to hate the orcs. Now they have reason to kill any orc on site - no mercy whatsoever. I can see the war becoming one of the central aspects of elven life for the next century or two, eventually quieting down either due to ennui* or due to running out of orcs to kill. Perhaps the orcs will even be driven underground as the drow were, although I doubt this, as Lolth will have her own reasons to hate and slay them.
* (After the last war between elves and orcs, I tend to think that a hot genocidal war lasted for centuries before fading into mere suspicion and hatred. Now it has flared up again, but I cannot see it lasting forever - merely a few centuries.)
I cannot see Lolth siding with the surface elves, but I can see her hating Gruumsh for killing the one she wanted to kill - especially now that she is a greater deity and so finally had the power to perhaps eventually meet the head elf deity as an equal, killing him herself. She would 'amuse' herself by having her followers kill any orc that dared to show its face underground.
I can see the human kingdoms being rallied by the elven lands, a call to arms to finally erase the orc menace of the north. The war would truly be a 'world war' due to the numbers of lands and peoples involved. It would be a vast crusade upon crusade, each lasting for a decade or three, perhaps followed by a 'rest' period of a few years or decades as they lick their wounds, repopulate their numbers - and rest due to having run out of readily found orcs to kill. Once the orcs regain a little of their courage and start moving openly again (even if only in familial bands - not even war bands), the crusade would start anew.
Caught between a rock and a hard place, most orcs would eventually die, although I doubt all would be lost. Some would survive, becoming a rare menace of wandering family bands and small tribes - like bugbears and ogres. Indeed, for a time half-orcs may all but replace orcs, as they might not be viewed quite as suspiciously as true orcs. Perhaps, given enough time, half orcs will even *replace* orcs, to the point that in some few centuries any tribe of half-orcs may consider itself to be true orcs, and speak with awe of the times of old when they were a stronger, etc people than they once were. The true orcs, in effect, would have become the legendary / paragon of old that is rarelyl seen upon the earth anymore.
In any case, as some have mentioned, with such vast genocide occuring, the orcish deities will fall greatly in power, reduced from greater to mere intermediate or even lesser, and those of intermediate to lesser or demideity. Lesser deities may fall to mere hero deities, and demideities may find themselves once again mortal. Either way, with the elves still strong, I can see orcish deicide becoming popular - to the point that perhaps only a few - or even just one or two - orcish deities surviving the coming purge. This will greatly change the feel of the orcs, their culture, etc.
Sure, the elves will lose a lot, but I tend to view it as orcs losing 75-95% of their numbers and elves losing perhaps 40-60% of their numbers. Remember, they have humans aiding them, and despite lower numbers they have more casters - and there are all sorts of elvish peoples in all sorts of lands that could be called to arms. I think in the long run the elves at least match the number of the orcs, but they are spread over a larger area, such that the orcs only ever run into a fraction of their number - and yet that fraction was enough to all but hold them back most of the time.
In any case, it looks to be an interesting campaign to come. Which world are you working in (Faerun, Greyhawk, Eberron, etc)?