There are already the makings of an alternative API:

https://docs.python.org/3.6/library/email.message.html#email.message.Message.add_header

There is also replace_header(), but it only replaces the _first_ header field, and leaves later ones untouched. However there is only __del__(), which deletes all matching header fields; there is no remove_header() or similar.

I think I would support deprecating the __setitem__() etc methods, perhaps with a cleanup of the alternatives, e.g. add remove_all(). Also, __getitem__() is equivalent to get(), which does not raise KeyError. Although according to Issue 12111, David said things are unlikely to change.