You can update aliases here, or on the node
or bulk update a whole bunch here
based on an alias pattern change set here
I imagine the reason it "Seems" like an alias didn't delete is because it have forwarding to another alias in a sort of chain. Drupal does clean up alaises on content delete, ou can do a simple test and see it happen. But if you have alaises chained it only seems to delete the final alais and leave the others. I think if you update you "update actions" you can minimize the number of extra alaises created.
Go here and find the section called "Update action"
You have three choices of what to do when an alais changes
- Do nothing. Leave the old alias intact.
- Create a new alias. Leave the existing alias functioning.
- Create a new alias. Delete the old alias.
Also based on there advice
"Considering installing the Redirect module to get redirects when your aliases change."
I hope this helps ans isn't off base but I faced similar issue on a site with 500k items and the clean up was a serious issue. Best of luck!