Thanks to the advice of a good man, I'll try to resume my point of view to avoid repeating once and again.
First, I find ground on our Policy:
> This declares a strong, but not absolute, dependency.
> The Recommends field should list packages that would be found together with this one in all but unusual installations.
Gnome can not work without GTK. But it can work without Network-Manager. Gnome and GTK will be found together always (at least, everytime Gnome is installed). Gnome and Network-Manager will be found together in all usual installations, but not on unusual ones. People who wants Gnome with all bells and whistles but find that Network-Manager does break their systems are not the core of our user base, but they are a considerable sector of it. Their installations qualify as "unusual installations" since they are not the majority, and they are enough to fire this rule. The rule does not distinguish between binary packages and metapackages.
Second, Debian is not Gnome. With this I want to make clear that Gnome view about what is and what is not core on their desktop (not to forget it's theirs) is important, but it should be not conclusive. Our duty as a distribution who cares for its users is to start with upstream software with upstream views and decisions, and the to put it together for a working set that fits our users. Sometimes we need to patch code, sometimes we need to remove pieces that are non-free, sometimes we divide codebases into several packages, for the sake of easing the management of Debian and the wellness of our users. As an example near to the thread, gnome nor gnome-core packages depend on Mono, while it is considered core by upstream.
Third, Network-Manager is not any other piece of Gnome. It should be trated differently from other like, say, Epiphany or Evince. Let's see the cases.
* For Epiphany, where epiphany-browser, which is a Depends of gnome-core, is installed in every (Debian) Gnome distribution, there are alternatives. If a user wants to use Chromium or Firefox or Konqueror instead, Epiphany will not interfere. User just installs the desired package (well, we do not provide Firefox as is, but a rebranded one that enhances my second point) and he's working. Also, if user wants to remove the unused epiphany-browser package, he can do so since there is a declared alternative Depends: gnome-www-browser, and if user has iceweasel or chromium installed he will be fine and nothing will break (not the same for Konqueror).
* For Evince, situation is a bit worse. It can be freely ignored if you want to use, say Okular or Xpdf, and it will still not interfere with you way of working, but you can not remove it without getting your whole desktop uninstalled. Anyway, since it does not annoy the user, it can be simply ignored.
*For Network-Manager, situation is very different. It breaks the network configuration of some users (a sensible fraction of), so it is not a simple case of "I want to use another program/method of doing foo". It is a case of "This program needs to go out of my system". It can not be simply ignored and an alternative used, since N-M messes with the alternative if it is installed.
Fourth, the chain that forces installation of netowrk-manager from gnome is quite curious. There are other chains that link even dpkg with gnome-manager like this one:
dpkg Sugiere apt
apt Sugiere aptitude | synaptic | wajig
wajig Sugiere reportbug
reportbug Sugiere claws-mail
claws-mail Depende libpisock9
libpisock9 Sugiere evolution
evolution Sugiere network-manager
But those are chains of Suggest, that are not installed by default. Instead, look at this:
gnome Depende gnome-core
gnome-core Depende network-manager-gnome
network-manager-gnome Depende network-manager
This is a quite stronger Depends chain, but carefully looking at it it happens that it jumps through a package that installs just an applet. I do not see how it is correct that an applet (network-manager-gnome) ends up breaking the network configuration deserves being a Depends chain.
Fifth, gnome-core is just core components. I do not see an applet fit there, an applet is more likely on "all bellas and whistles" space, so it should not Depends on network-manager.
Sixth, the amount of work needed for Debian to have gnome-core Recommends network-manager-gnome is minimal. The amount of work saved for our users (those of them who need to get rid of network-manager) is enormous.
Seventh, the user by user solutions previously proposed on this list do not fit majority of our users. I'm very happy that our developers have such a level of familiarity with packaging tools and scripting: that makes Debian a better distribution, but our users do not have such skills. If a user asks me how to get rid of that manager that is messing his network while still having his Desktop, I want to be able to say him "Write this command and you're done" instead of
> - Grab the control file of the meta-package
> (~1 line in shell, use grep-aptavail)
> - Filter out unwanted packages from depends
> (~5-6 lines in shell)
> - Create a local package, under a different name, with the updated
> (~10-20 lines, use equivs)
> === 5 minutes so far ===
> - Push it into a local repository
> (~2-3 lines, use whatever, reprepro, mini-dinstall, or cat <<EOF)
> - Put the local repo in sources.list
> - apt-get update & install your shiny new meta-package
> - Hook all that into Apt::Update::Post-invoke
which is absolutely unfit for our users.
Eighth, use cases are like these:
a) Novice user with a laptop. This user installs Debian once, with Gnome, and network-manager helps him to connect wired and wireless. He uses only high end, probably graphical package managers.
b) Novice user with a desktop. This user installs Debian once, with Gnome, and network-manager does not help sensibly, since a simple 'iface etho inet dhcp' stanza will make him the same service, but it does hurt. He uses only high end, probably graphical package managers.
c) Advanced user with a laptop. This user installs Debian several times, and maybe follows the bleeding edge of sid. network-manager helps him to connect wireless, but pisses him when he tries to connect a smartphone. He uses aptitude and some times apt-get.
d) Advanced user with a desktop. This user installs Debian several times, and maybe follows the bleeding edge of sid. He does not need network-manager at all, but can live with. He uses aptitude and some times apt-get.
e) User a fixed IP system. This user does not need to be skilled in Debian, but has probably installed it a couple of times. It may be that he runs a home web server, or just that the system needs to be available via ssh. network-manager does not mess his network configuration, managed from /etc/network/interfaces, but his applications like Pidgin or Evolution do not work. He feels comfortable with aptitude and maybe grokking a bit, but he is not a Debian packaging expert.
f) Network admin with bridges and other nonstandard configrations. network-manager do not fit him at all. He feels comfortable with aptitude and maybe grokking a bit, but he is not a Debian packaging expert.
g) Debian developer. He has installed Debian zillions of times, just for the sake. He is proficient both with aptitude and scripting dpkg, and he is a Debian packaging expert.
Let's review for each of these cases the impact of both Depends and Recommends:
a) This user uses a package manager which installs Recommends by default. He will be as happy with Depends as he is for Recommends.
c) This user uses a package manager which installs Recommends by default, but knows how to remove a Recommends package if needed. It is up to him to decide if doing so or not. But as the system works as-is, he will be as happy with Depends as he is for Recommends.
e) This user having a Depends will not be happy. he wants his system, up and running, with all applications up and running, including Evolution, but Evolution does not work. He has no options: he can not remove network-manager without having his entire desktop removed, but also he can not use a custom package without the dependency or with equivs. But this same user having Recommends will be happy, as he just does "aptitude remove network-manager", network-manager-gnome gets removed as well, and he's done. Nothing else removed (besides maybe some libs). Evolution starts working magically.
f) Mostly same, but he needs network-manager positively out of his life. This user can even think on running "dpkg -P --force-depends network-manager network-manager-gnome" after each "aptitude install" run.
g) This user is able to cope with whichever solution, including custom packages.
I think use cases e) and f) are a fraction important enough of our user base.
As a side note, I would create a different package myself, but I think I'm not skilled enough (I maintain only two low-movement, no code packages). I'm an example of use case f, and solutions previously given on this list do not fit me.