Вы можете сделать выборку, которая ищет все строки, которые существуют в таблице, и помещает их в список. После того, как вы проверите, какие строки не существует.
Пример:
var foundItems = tableToCheck
.Where(x => hugeList.Contains(x.id))
.Select(x => x.id)
.Distinct()
.ToList();
var notFoundItems = hugeList.Where(c => !foundItems.Any(x => x == c)).ToList();
Таким образом, вы делаете только один запрос к БД.