I'll give you credit, but how much?

As for what code needs to be audited for SELinux to work as it's claimed to, that's not really useful in reality, as:
1) Development on the kernel would have to stop (or the code would have to be audited constantly, which isn't cheap)
2) Auditors aren't perfect
3) The problem is architectural; as James said further down on this page (the first time I've seen an admission like this from anyone at Red Hat, but my memory may be wrong): "SELinux cannot be expected to protect against kernel vulnerabilities, because it is part of the kernel."

Indeed, most vendors exaggerate the abilities of their products. The most egregious example I can think of right now is anti-virus software; but being as the parent article is about SELinux, I talked about SELinux (with some mention of Xen and VMWare as well).

Regarding "Brad might be [...] perhaps picking on Linux or FOSS because he has allegiances elsewhere. [?]", as I (and the PaX team too for that matter) have spent just about every day for the past 8 years working on free software to improve Linux security, that's a little insulting -- but I imagine you weren't aware of that (no problem).

I don't know of any provably secure OS -- surely it wouldn't be anything like the OSes people actually use if one did exist. It's not really useful to entertain this idea; what's useful is thinking about how to improve things in ways that don't add complexity or burden on a user. Achieving higher levels of security is useful, raising the cost of developing an exploit by making exploitation techniques more difficult and complex is useful.

It's especially important now with the 2.6 development model (moreso than it was with the 2.4 series of kernels) that greater considerations be made for security in the kernel itself. I've mentioned this on previous articles, but it goes without saying that when you have a ~80MB patch of new code/changed code/removed code every 3 months, there are a lot of vulnerabilities being introduced. It's been made clear by the kernel developers that there's no intention of changing the development model, so instead of just accepting the problem and continuing in the "fix vulnerabilities that get reported to us, release a 'stable' update once a week" mindset, something more can be done.

You mentioned "weaker links than an SELinux" -- I don't know if there was a typo involved there, but I don't want to give the impression that SELinux is a weak link. Considering the length of time it's been around, its code quality has been better than most, with only a handful of vulnerabilities reported (though some were silently fixed, like the remote DoS from 2005 (I think) that I mentioned several months back. It was discussed among the vendors on a private list, noting that attacks had been seen in the wild, but still no CVE or announcement was released -- I assume because at the time the attacks had been discovered, the bug had already been fixed). Restricting what files, etc a process can access is useful too as not all vulnerabilities involve memory corruption/arbitrary code execution. In that respect, it's a good complement to the NX+ASLR protections already in place. But again, it's important to realize the limitations of the technologies so that levels of risk can be properly evaluated.

-Brad