Thanks for all the responses to the question that I posed. The reason I posed it is that I've been seeing a lot of language requests coming through the MSDN feedback site, which is a good thing, but some of them are pretty obviously impractical, so I wanted to try to explore a little of the "language designer" mindset.
Several people pointed out that Cyrus had blogged about this a while back. That's true, though he doesn't explore things from a language designer standpoint, but rather from a language user standpoint. That's a nice place to start, but it doesn't really explore the areas you need to explore when thinking about adding a language feature.
So, here's my analysis of the request. Note that I'm only one member (so to be an ex-member) of the language design team, so there may be other opinions...
If you truly want to support non-null types, they need to be a runtime feature. That's the way that you get a secure, easy-to-use system that works the way users would want it to work.
Unfortunately, at this point in time, it would be somewhat difficult for the runtime team to do it. Even if they did, it's really not practical to modify all the existing libraries to take advantage of such a feature, as that would pretty much require that every bit of .NET code be revisited/recompiled. If you changed String.IndexOf() to only take a non-null string, think of how many places that's used in the .NET universe.
If we had it to do again, creating the runtime and CLR with such support seems like a good thing to do, but we weren't sharp enough to figure that out early on, so it's not something we can realistically add at this point.
So, where does that leave us? Well, it is possible to approach this from the "parameter validation" perspective rather than the "not null type" perspective, and you can likely get the effect that you want (ie not having to write your own parameter validation code), though it's decidedly less efficient to check for null everywhere than to just know that null is not a possible value. We will be talking about the parameter validation scenario in future design team meetings.
I think that Daniel O'Connell and Matthew W. Jackson probably came the closest to how I would approach the issue, so 250 points to each of them.