Short answer: importing nodes and deleting nodes no longer included in the feed needs to happen with the same importer.
When performing an import, Feeds indexes the imported items in the feeds_item table. Each item in this table belongs to a specific importer and - in case the importer was attached to a content type - also to a specific feed node.
When the importer is configured to clean up items that are no longer in the feed, it loads all item ID's into memory for that specific importer (and feed node) at the start of the import. During the import, Feeds crosses of each item from the clean list that it has seen.
At the end of the import, it cleans up the items that remained on the clean list.
When you use one importer to import a list of items, these items are then owned by that importer. When you then run a second importer for the same content type, it will own none of the items that were created/updated with the first importer at the start of the import. If the second importer doesn't own any of the items, there is nothing to delete after the import.
Note: ownership of items can be "transferred" from one importer to another. For example: items that were originally created by importer 1 and later updated by importer 2 are then owned by importer 2. If importer 1 updates them later, importer 1 owns them again.
So using two importers to update the same content makes the "delete non-existent" feature unpredictable.