I found out that this can be accomplished by using the paging functionality of the entitycollections, typed views and typed lists (RTFM!)
This is how I do it:
ContactsTypedView contacts = new ContactsTypedView();
DateTime lastExportDate = GetLastExportDate(ExportType.Contacts);
IPredicateExpression lastModifiedFilter =
new PredicateExpression(ContactsFields.Lastmodified > lastExportDate.ToString("yyyy-MM-dd"));
int amount = contacts.GetDbCount(false, lastModifiedFilter);
int pageSize = 1000;
int remainder = amount % pageSize;
int pages = (amount/pageSize);
if (remainder > 0) pages += 1;
for (int i = 1; i <= pages; i++)
{
contacts.Clear();
contacts.Fill(0, null, true, lastModifiedFilter,null,null,i,pageSize);
//do magic here
}
But my question still stands: what about records that are inserted into the set that I'm fetching in batches?