batch api for large batches
Batch API in Drupal 6 serializes everything into one row, causing the problem you've seen.
You need to do manually what Batch API does for you automatically in Drupal 7: use a queue.
The Drupal Queue module is a Drupal 6 backport of the Queue API that is in core for Drupal 7.

Basically, queue the items you want to process, and then only pass the queue ID to Batch API. 
Batch API then fetches the queue and processes the queue part by part until it's done.
See batch_example_batch_2 from the Examples project for reference.

The Examples project also has an example module for queue usage, see:
http://drupalcode.org/project/examples.git/tree/refs/heads/7.x-1.x:/queue_example