I deleted multiple entities from my diagram but they still exist in the model explorer and in my model. 

For example, my model has the entities MOVIE, STORE and CUSTOMER deleted only from the diagram. They still show in the Model Explorer.

Figure 1.

I created a new Subject Area with the name of TEST SA and moved those 3 entities at the same time:

Figure 2.

Figure 3.

Solution: Create a new diagram with the name of NEW DIAGRAM and select the same entities as above to be in it.

Figure 4.

Figure 5.

Press CTRL+A to select all of the entities in the Diagram:

Figure 6.

Press Delete:

Figure 7.

You will be asked whether you also want to delete those entities from the model.

Respond YES.

Figure 8.

If the message in figure 8 does not show up, go to Tools | Options and click on Reset all Messages and perform the delete action again.

Now the Entities will be deleted from the Model and will not show up in the Model Explorer.