Can't see your code but immediately what came to mind is spreading out machine ids across API calls so you stop guessing early for ones that have low seq numbers, might speed things up if I understood correctly?
Most of the time, they won't get above sequence id 0 -- I don't know how sequence ids are allocated but I suspect it would be sequential for each server. For instance, machine id #123 happens to process two tweets in the same millisecond, the first will get 0 and the next 1