Client applications typically poll for changed data periodically. Polling involves the following considerations:
5000 * number of licenses in the organization
For example, an organization with 1,000 licenses could have up to 5,000,000 (five million) records in the delete log before any purging took place. If purging has been performed before your getDeleted() call is executed, an INVALID_REPLICATION_DATE error is returned. If you get this exception, you should do a full pull of the table.