Remove the URL aliases that don't have a node
A core bug causing this error was fixed for Drupal 8.2 and 8.3:

PathItem::delete() never runs because the path field type is a computed field in disguise

The fix for this problem, then, should simply be updating Drupal (...after having waited several months for this fix to be made and 8.2 released— but a satisfying answer now, i hope!)