How to speed up Batch API Operations?
This doesn't work for contrib code, but if it's your code and you know it well, I recommend writing a drush command to do the work.  Within drush, limit drupal_bootstrap() to the appropriate bootstrap level.  I can't recall the actual numbers, but a very large percentage of time for every drupal request is spent in bootstrap, and you can save a lot of time there.

Furthermore, check out the guts of the Migrate module.  I don't know how it does it's mojo (never taken the time to grok it), but it can blaze through huge batches of nodes very quickly.