In case it makes a difference, the site I'm working on uses Drupal 6. The queue I'll be creating will check a batch of user accounts with a REST API, to verify whether the users have logged into another system. Until the API gets updated (hopefully soon) each user requires a separate request, which is why I'm batching them.
Drupal Queue is a backport of Drupal 7's queue API for Drupal 6. It provides basically the same features as Job Queue. However a big advantage with Drupal Queue is that it uses the same API as Drupal 7 Core. This means if your module uses Drupal Queue in D6, your upgrade path to 7 will be effortless.
Another module to consider is PubSub.
Unfortunately I have only used PubSub before, not the others, so I can't compare them. If I were coding this, my first attempt would be to "publish" the users and have a drush command that would run periodically that would "subscribe" and handle them in batches.