Deleted categories still show in post meta box

I deleted two categories in the categories menu on my WordPress site, however they are still showing in the ‘All Categories’ tab on the categories meta box within a post. I can select the category in the meta box but it never shows in the main category menu.

Anyone have any ideas why this happens and how to get rid of the supposedly deleted ones?