I honestly have no idea what's going on there. Joomla automatically generates all SEF URLs on the fly, so if something was trashed, it shouldn't be considered anymore. However, if you are using a 3rd party SEF tool, those usually store the SEF URLs in the database. In that case, even if you delete a menu item, the old SEF URLs may be used since the route was already created and stored in the database.
Beyond that, I'd check to see if you have any articles or categories with that same alias that may be being used as well.
I hope that helps,
Alex
Forced SEF path
