Customers have to use Member of Smart List as indirection for the desired filter condition. i.e. Create a new Smart List with the "Deleted from SFDC" filter. Then change this failing flow step choice to use 'Member of Smart List' with the Smart List just created.
Example flow step: