Queue overpopulates if cron gets behind

I've been doing testing of the module locally on a site that has ~30,000 nodes that need social stats checked. On average, it is taking 1-2 seconds (occasionally up to 9!) per node to gather the stats. I noticed the queue table was rapidly filling up and realized that was due to every time cron runs, all 30,000 nodes are added to the queue table, even if they previously exist in there and just haven't been reached in the queue yet. Ideally, we'd setup a good combination on the production server to balance how long it takes to check each node vs. how frequently and long cron runs and processes queue items (that's why I made this Minor). However, relying on that balance seems risky.

The important code for this is here:

    // Fetch node id and type for the content types,
    // which has at least one social media selected and
    // which are created after the date mentioned in module's configuration.
    $query = db_select('node', 'n')
              ->fields('n', array('nid', 'type'))
              ->condition('n.type', empty($content_types) ? '0' : $content_types)
              ->condition('n.created', $start_date, '>=')
              ->execute();
    $queue = DrupalQueue::get('social_stats_update_stats');
    while ($result = $query->fetchObject()) {
      $queue->createItem($result);
    }

There are a few options for how to optimize this - not sure which is ideal so would be glad for any input here.

Start fresh approach - remove all remaining in queue, add all back in
Start recording every node processed in the social_stats_total (not just those with a count greater than zero) and also add the changed column to that table. That way we can order the nodes before they are added to the queue so it does the ones never processed first, and then the ones processed the longest ago next. This would work in conjunction with either expiring or just straight removing every item in the queue placed by social_stats prior to that run.

Pros: Easy way to make sure we don't fill up the queue with entries and that they are processed in a logical progression.
Cons: It is still a lot of queue items to create every cron run which can lead to issues like running out of auto increments since it is an integer primary key field (max number 2147483647 so a site with one million nodes, running cron four times daily will start getting database errors in under a year and a half)

Check for remaining queue items?
First check the queue table to see if there are any remaining social_stats items and - if there are - skip adding more.

Pros: Incredibly easy to implement.
Cons: If you had only one node, or just a handful of nodes remaining in the queue, this could effectively "waste" a cron run that could have been used to update more nodes.

Recursive queuing
Not so certain about this one, but maybe define something like a "social_stats_reseed_queue" type which is added after all the "social_stats_update_stats" ones are added. It is responsible to re-fill the queue, so it only gets run once the current items in the queue are all finished. It would work in conjunction with the cron hook and the "social_stats_cron_interval" variable to make sure it doesn't seed the queue too soon, but respects the social_stats_cron_interval setting.

Pros: I am not intimately familiar enough with the Queue API to know if this is a bad idea or a good one.
Cons: Introduces a little more complexity, but not super significant.

Queue tracking
Like the first approach above, this would require recording every item in the social_stats_table even if the count was zero and including the changed column. Additionally, it would require storing those items before they are added to the queue. This is because we would also add a column called queued that records a timestamp for when the item was added to the queue. Then we can compare if the changed timestamp is older than the queued timestamp and skip adding a duplicate for those.

Pros: Fairly easy to implement, and seems logically straightforward.
Cons: It might be able to be optimized, but off-hand it seems like the updates to record the timestamp when adding nodes to the queue might defeat some of the purpose of using the queue in the first place.