How to handle “not label Y” in a multi class machine learning problem?
I think you should start by looking into Multi-label Classification, as your problem seems to be a subset of MLC, where one example can have multiple correct labels. If one class is "Pictures with people in them" and another is "Pictures with guitars in them", one picture could certainly belong to both - this is an example of multi-label classification.

In your case, you could formulate your problem by considering that most examples have only one appropriate label, but 'Not A' has four: 'B', 'C', 'D', and 'E'. (If you have more specific information about the possible distributions of the correct label, you could use that information here too)

There are several methods for MLC, not all of which I'm familiar with, but I know plenty of research has been done on this using the CelebA image dataset, for example (it comes along with a number of potential label vectors). 

Good Luck, and welcome to the site!