Hi,
I'm a bit surprised to see Stephen King and H.P. Lovecraft mentioned in relation to New Weird. "New Weird" has little or no meaning, if you view it as a literary genre (although you could describe things they have in common, I suppose).
As far as I'm concerned, the story of "New Weird" starts in the sixties when Michael Moorcock takes over editorship of a genre mag called "New Worlds". This collects a couple of writers around a single mag: Moorcock, Ballard, Aldiss, Harrison (both M. John and Harry), Sladek... Soon, you hear the term "New Wave". I'm not sure when and where this originated. Generally, the term tended to be used more often in America (Judith Merrill, Harlan Ellison's Dangerous Visions anthology). I think the New Worlds crowd themselves didn't use the term consistently, but I'd have to look more deeply into this.
The basic tenet of New Worlds was to marry "genre" with "the literary mainstream" and not to let genre borders determine the story. You'll have to realise that Lord of the Rings only became really popular in the sixties; the "New Worlds" crowd's father figure was Mervyn Peake (and to a lesser extent, Lieber). Two genre streams emerged, basically, and they're in competition - sometimes playful, sometimes fierce - until today.
In the 90ies, the "New Worlds" mag was revived as an original anthology series, with Dave Garnett as editor. Moorcock was involved. So was Aldiss. Among the newer authors that regularly appeared were Paul diFilippo, Ian MacDonald. (If you can find those, they're well worth reading.)
Of the original New Wave authors, the most glaring omission was J.G. Ballard, who's pretty much gone mainstream these days (without changing his style too much - quite a feat!). Another author you didn't find in the new New Worlds was M. John Harrison.
In this decade, M. John Harrison published Viriconium, a collection of stories, some of which were originally published in the old New Worlds. Around this time, I think, people started talking about "New Weird". M. John Harrison was the veteran, Mieville the "new blood". And as always, they played around a bit with the term, until everybody started using it and it became too restrictive, at which point they start to distance themselves from it.
"New Weird" may be a lot of things, but it isn't new. New Worlds, New Wave, New Weird, Now What? It's basically a couple of people, historically linked, who care about style as well as story, tend to have socialist tendencies, and prefer Peake to Tolkien. None of this is obligatory. Sometimes they play around, and sometimes they are politicking. They all emphasise creativity over convention, though.