Redid CaseInsensitiveDict to work correctly/sanely

Fixes #649, #1321, and #1329. Don't merge yet, I want to get
some opinions about this implementation.