One of the perennial debates (on the Hungarian Wikipedia, at least) is whether to delete redirects from old names in the project namespace. On one hand, even when links are updated, it destroys some navigation pathways (bookmarks, external links etc.), makes old revisions of pages (where the links are not updated) less readable and annoys some people; on the other, the old (and often erroneous or misleading) names clutter up the search suggestions dropdown, which is by far the most user-friendly navigation method currently). There is a similar problem with redirects from misspelled names of articles.
It would be very useful to have a __NOSEARCH__ magic word which would suppress indexing of such pages by the internal search engine (or maybe just adding a flag so that the page is only returned when such pages are explicitly requested).