An alternative 'simple' avoidance (more of a hack, perhaps) would be to switch to a specific binding (perhaps some daemon could have the job of handing out fd's to legitimate mounts of such directories; perhaps a specific binding of the whole hierarchy, or a specific binding of particular often-security-important directories) whenever the current binary detects that it is setuid. (Obviously, its children would inherit this as usual.)
If you consider /etc, /lib, /bin, /etc /sbin, /usr/lib, /usr/bin, /usr/sbin and /usr/libexec 'security-important', then bingo, all the 'read an /etc/passwd of your own design' or 'force a setuid binary to run a new binary of your own design' attacks become impossible.
Downsides: an arms race for 'security-important directories' much as there currently is for security-important environment variables. If you rebind the whole tree then people might find that setuid apps could no longer operate on stuff in the user's own hierarchy (as soon as non-superuser mount() becomes possible), which would be seriously counterintuitive. Depends on a new daemon, but perhaps that could be the same one that does service invocation, so the same thing could provide a means of secure setuid app invocation *and* make old setuid apps more secure in the presence of user-defined mounts as well.
Perhaps what you want the 'privileged mount daemon' to do is to hand out new mounts to all filesystems not marked as 'user' in *its* /etc/fstab: that way there would be no arms race for 'security-important directories' and it would be impossible for a user to fake it out by rebinding the /etc/fstab.
This could easily be done by ld.so (except that getting this change past Ulrich is probably impossible: it feels overdesigned and fragile even to me).