Not hard at all:

#REDIRECT [[Sayre's law]]

Well of course. Somebody has done that now for that page it seems, but the general problem still exists: http://en.wikipedia.org/wiki/Parkinsons_Law_of_Triviality

The idea would be to make mediawiki itself automatically preform reasonable redirects when pages don't exist.

It doesn't even need to redirect - it could just automatically include some search results if the page doesn't exist.

>The idea would be to make mediawiki itself automatically preform reasonable redirects when pages don't exist.

Mediawiki does do it automatically, it's called having many thousands of users.

The Wikimedia Foundation wiki's might have that many uses, but I'd say most installations of mediawiki do not.