SOQL ignores null checks on required lookup fields:
Suppose you have one object and some of the records are there on that object. Now when you create one new Lookup field and make it required that means all the existing records will have a null value for that new required lookup field.
SOQL seems to expect that required fields can never be null. so, it ignores null checks on required lookup fields.
The following line does not return any results:
SELECT Id FROM MySObject__c WHERE RequiredLookup__c = null
When you set the field as not required then the same query returns the records.
To get the results in the query you can tweak it a little bit:
SELECT Id FROM MySObject__c WHERE RequiredLookup__r.Id = null