Edit: The other answer provided is much cleaner, better and uses only standard functionality. If for some reason you have run out of external Ids my much more complicated approach my work for you, but I would instead raise a question with SalesForce to see if you can get the limit raised for your object.
Regarding your comment in the context of the question I believe what you need is to bulk query all possible matching "MyCustomObjects" and place them into a data construct, using a FirstName LastName key. Here is one possible way of achieving this goal:
public static Map<String, MyCustomObject__c> createNameToMyCustomObject(List<MyCustomObject__c> myCustomObjects){
Set<String> firstNames = new Set<String>();
Set<String> lastNames = new Set<String>();
for(MyCustomObject__c myCustomObject:myCustomObjects){
firstNames.add(myCustomObject.FirstName__c);
lastNames.add(myCustomObject.LastName__c);
}
List<MyCustomObject__c> foundMyCustomObjects = [
SELECT FirstName__c, LastName__c
FROM MyCustomObject__c
WHERE FirstName__c IN :firstNames AND
AND LastName__c IN :lastNames
];
Map<String, MyCustomObject__c> nameToMyCustomObject = new Map<String, MyCustomObject__c>();
for(MyCustomObject__c foundMyCustomObject:foundMyCustomObjects){
nameToMyCustomObject.put(createMyCustomObjectNameKey(foundMyCustomObject), foundMyCustomObject);
}
return nameToMyCustomObject;
}
public static String createMyCustomObjectNameKey(MyCustomObject__c myCustomObject){
return myCustomObject.FirstName__c + '-' + myCustomObject.LastName__c;
}
You can then use the created map in conjunction with createMyCustomObjectNameKey method to check to see if the object exists in the database.
if(nameToMyCustomObject.containsKey(createMyCustomObjectNameKey(myCustomObject))){
//object with first and last name combination exist in salesforce
} else{
//object with first and last name combination does not exist in salesforce
}