You might also take a look at the Thieves World setting from Green Ronin. Sanctuary is pretty grim and gritty and there are enough areas throughout the land that are open for DM development. It also has some rules variants for magis and such.
I like the Wilderlands as well, grim and gritty as you want it to be and tons and tins of room for DMs to develop it to their own tastes. Not a lot on rules variants though ( afew in the Players Guide and the City State of the Invincible Overlord book but not much), however, it can fit well with rules from a system like Iron Heroes adding tot he level of grimness and danger.
I like Goodman's Aereth a lot. It may be a bit too classic fantasy for your tastes though, and lacks alternate rules, but has lots of undeveloped areas to work with, and some areas (the Scourge, the Lostlands, parts of the Southlands are very grim and can have that dangerous feel.
The classic Blackmoor setting might hold some interest for you as well. It has alternate magic rules for focus casting, and some other bits, danger abounds making like dangerous and lots of the settting can be fleshed out as little is described in any level of detail yet. Various threats from the Egg to the Afridhi make life dangerous, and life can be brutal in this frontier territory. The corebook was originally distributed by Goodman but was produced by Zeitgest games who now distribute it as well. It has the pedigree of being the orginal setting of D&D co-creator Dave Arneson as well.
The sofrementioned Midnight might be a good choice as well. I liked it, but your group really has to buy intto the core concept of life in a world where the Darklord has won for it to work. If they like the concept, it can be a great game, but if they chafe under the limitations of that, it might get ugly.
Along those lines, Troll Lord Games Codex of Erde detals a world that is just emerging form the yoke of a fallen Dark Lord. Lots of areas described but not in detail, so there is plenty of room to expand. Life is brutal and short in the aftermath of the war to defeat the Dark lord, and the setting is rife with mythic overtones. Originally released for 3.X D&D, it is currently being retooled for TLG's C&C system.
I like the locales for the Necromancer Games setting (Bard's Gate et. al) and there is a lot of room to detail what you want as well, but it is not a full settiing like you are looking for. That has some drawbacks, but also some benefits if you are trying to mold the setting into what you want, these can be a toolkit to build from, but there really isn't any alternate rules here, but again you can import those from an Iron Heroes or similar rulesset if you chose. I know I built on the framework of these locales when I wrote Shades of Gray for Necromancer to flesh out the setting as the backdrop for that series of adventures.
-M
-M