Maybe we can change this whole method to this:

      def reject!(&block)
        ordered_keys = @ordered_keys.dup
        ordered_keys.each do |k|
          if yield k, self[k]
            ordered_keys.delete(k)
          end
        end
        ordered_keys == @ordered_keys ? nil : @ordered_keys = ordered_keys
      end


The advantage is that we're not dup-ing self, we are only dup-ing the ordered_keys and then swapping them with self's @ordered_keys if they differ.
What do you think?