non ho provato ma se non ho capito male ti serve qualcosa tipo questo in ef.

codice:
var query = ctx.TabellaA
                .Where(a => a.TabllaB
                    .Where(b => b.ID == parametro).Count() == 0)
                .Select(a => a.ID); //opzionale se ti servono solo gli id altrimenti .ToList()
in questo modo ti seleziona tutti gli id di TabellaA che non sono associati allo specifico record di TabellaB.

Se sei un patito delle performance e guardando sqlProfiler non sei soddisfatto puoi sempre scrivere una stored procedure direttamente in sqlserver, importare quella dal designer e usare la SP direttamente in EF.