Hi Guy_Shlomo,
Was trying to reproduce the issue and couldn't get the same output as you see , could you please check if you see the below behaviors with a different Operators and Type of the query.
1. Check what behavior you see if the Type of the query is "Flat list of work items"

2. Check if you only see "Removed" items if the operator is either "=" or "Contains"


3. Check if you only see items with status other than "Removed" if the operator is either "<>" or "Does Not Contain"


Hope the above information helps.
As @AmanGarg-MSFT listed out , if you are still seeing an issue please reach out to the Azure DevOps community forum. Thank you
https://developercommunity.visualstudio.com/spaces/21/index.html