Why do they need so many magic levels? They (or rather, most Evil lists via the Nazgul that count as part of their lists) are pretty exceptional in terms of the levels they can pack in due to the sheer cheapness of their level 3 casters. I think making them level 1 is too much, but at the moment they are they only models at that point level with that many spells available. It makes no real difference when there is one or two Nazgul but becomes pretty significant when three plus at 1000 (or five for 1500) and the spell output becomes reliably more than their opponent's ability to mitigate it. The special abilities some of them have on top of this is just an added level of 'wrong'. I am not sure how in this day and age, game designers did not stop to think that giving 'open ended' abilities (ie applies to a whole formation) might be a bit problematic, especially when more than one could be stacked.
Even without Nazgul being over the top, Mordor will still only be 'burdened' with being a list with access to great and affordable heroes, 25 pt Str 4 heavy inf, massed 2HW Orcs to go with their Darkness/Ruin Spells, very nice heavy cavalry an elite heavy inf unit with str 5 and Berserk, 50pt arty, as well as also having all the more normal things that other lists get! - I think they'll manage.
This is not to say that I'd be looking to boost any other heavy inf based army either. Other lists are in more need of a little lift IMO.
I don't see many Winged Nazgul around, if anything they are perhaps too vulnerable for their points vs Good casters.