do you wipe bayes database often? If not, it's not needed to retrain on all messages, since they are not forgotten.
I don't recall ever deleting the DB. It's my understanding that sa-learn remembers which messages it's learned before, but it makes sense to remove them periodically to an archive to reduce the load figuring out that they've been seen before.