Resolve issues 4366 and 4420 for better patch performance

I rebased the last two commits here on another change in my PR for branch 'test'. If you take this PR no need for that one. The test changes were necessary but otherwise unrelated, so they were a separate commit.
Why not use the indexer all the time and skip the ContainsKey check? Probably boils down to similar code in the BCL...