So I figured out one really strange thing:
When I delete the criteria and create the exact new one, suddenly its working.
So this seems to me as a BUG.
Something else is working too. If I open the filter and click save without changing anything, the filter is suddenly working fine.