Depending on the capabilities of your integration, you might first consider making the changes on that side. If you have somewhere to store the email ids you've seen on the integration, you can simplify that by just checking your local store while preparing the update.
To populate the list, even with very large orgs you should still be able to pull down all the contacts using the bulk api without exceeding the API limits. However, depending on your orgs data volumes that may not be terribly efficient. The web services API has
getDeleted calls which you can use to update your cache. You might also take a look at the Streaming API if you want to update the cache in real time.
There are probably a number of hack-ish approaches with triggers that you might also consider. For example, adding a trigger that fails all inserts for the integration user (make sure the integration allows for partial DML success). @JeremyButler also suggested using a intermediate object with a trigger to copy it over to contacts if it meets your criteria.