[doomjunky]

Assuming that sequential IDs are handed out sequentially. Assuming further that gaps in this sequence indicating deleted tweets.

You could reduce the sequence ID space by employing the fact that it is overall less likely that a tweet is deleted than otherwise and a sequence of two CONSECUTIVE deleted tweets is even less likelier.

E.g. If you find sequence ID 0 but don't find 1,2,3 than you can probably skip 4,5,6,7. I don't know the probabilities of deleted tweets, but i am sure someone could calculate it to determine the 99% threshold.