How about logging the failed "Go" queries on the server and ranking them? Searching the Wikipedia can be pretty frustrating at times, especially when you don't know exactly what you're looking for. You know what I mean, you *know* what you're looking for, you just don't know what exactly it is called, especially when that's an article which can have a lot of names.
Once the queries are logged and ranked, a relatively simple mechanism could be built to pick one of the top 100 every couple of hours and show it somewhere in every page, obviously as long as the article hasn't been already created. That way we increase the chances towards meaningful pathfinding (#REDIRECTs) and *really* "wanted articles".
I'm aware this would incur a tad more load on the server, but since people typically tend to follow links rather than search for stuff, I don't think this would be a serious performance hit. What do you think?
--Gutza