delete from url_alias_extra as well as creating the entries

delete from url_alias_extra using url_alias_extra left join node on node.nid=url_alias_extra.entity_id where node.nid is NULL;

it clears out the url_alias_extra table, for nodes that have been deleted.

Might be a good idea to fix the cause though :-)