I just figured out, that SOQL ignores null checks on required fields. It seems to expect that required fields can never be null. In my case it's a new field, so a bunch of records actually have null values.
System.debug([SELECT Id FROM MySObject__c WHERE RequiredLookup__c = null]);
does not give any results.
But as soon as I set the field to NOT required I get my results.
Any one else experienced this? Any simple workaround? I don't want to query all records and do a manual check.
Edit:
Since some of you don't belive it, I reproduced it with a lookup to Account, see screenshots with debugs:
switch requirement off and run it again