Deleted items being returned in queries

Think this may have been since the 16th Oct release but can't be sure. I've noticed some of my queries are showing 'Deleted item' in my query results. These are objects that still meet the properties criteria (e.g. linked to the current object in the cases I'm seeing) but have been deleted. To clear them I'm having to undelete that object, remove the link, and then re-delete the object.