Might want to base it off of http://www.mediawiki.org/wiki/Extension:TitleKey and share the same index table. Note that the search-suggest is already case-insensitive. Not sure if that's because we have a Lucene backend (in which case... can we just use that instead of a separate index?) or if the table already exists. Might still be worth installing the extension because it case-insensitivzes(?) the OpenSearch too. Ours currently is case-sensitive.
Add case_folded_title column to page table in the database... or a separate table as per TitleKey (on dev).
Create & run a script to create the case-folded versions of all titles.
Make sure that case-folding works with foreign characters (including simple ones such as Ü but also complex such as asian characters). See mb_strtolower($str);.
Find a list of all of the only-changed-case redirects and delete them with a bot.
Create a list of all of the currently-existing conflicts which would cause key errors.
Fix the conflicts in dev.
If a page does not exist, but a page exists with the folded-case of the same page, use that (should be similar code to implied-redirects).
If moving to a page which already has a page with the destination's case-folded title, disallow this... unless: (next item)
If moving to a page which has the same case-folded title, allow this.
Disallow page-creation of articles with duplicate case-folded titles. For the most part, this won't happen to users because they'll get redirected first, but it could still happen.
Verify that the canonical page name in the meta tags is correct, otherwise search engines will penalize us for having duplicate content (worth verifying this on normal redirects and ImpliedRedirects too).
Make sure the parser's red/blue linking colorization links anything which has a matching case-folded page.
Change API to use the case-folded version (but keep the existing code around somehow, so that we could switch back by using a config setting). This would be a good time to test that code which extracted the fuzzy finding of pages to be its own function (could just use diff sub-functions for case-sensitive and case-insensitive dbs).