Ooh–good call. This and Coraline have got to be right up there.
China Mievilles’ Un Lun Dun would probably fit the bill:
That world was based on Arthur Machen’s “The White People,” one of the greatest supernatural stories ever written, according to me and some guy named Lovecraft. I don’t see that world as being particularly “dark” so much as “other.” The evilness and eeriness in the story is based on the naiveté of the young girl who’s being drawn into it.
How about the Fairy Land of George MacDonald’s Phantastes? The TREES there’ll kill ya.
Come to think of it, the trees in Lord Dunsany’s The King of Elfland’s Daughter are homicidal, too.
Clive Barker’s* Imagica*, although some of it takes place on Earth. Earth is only one of the Dominions though (there are 5). The First is where the Unbeheld (God) lives. 2 of the main characters travel through the others, tracing Hapexamendios’ (the Unbeheld) historic journey through the Dominions. It’s part fantasy, a lot horror, with many fantastical places and creatures. I’d also have recommended Weaveworld, but it contains “hidden/secret places on earth” so that’s out.