¿Cómo puedo recursivamente bzip2 todos los archivos que no están comprimidos?

encontrar es tu amigo. Creo que lo siguiente debería hacerlo:

find <target_dir> -not -name \*.bz2 -exec bzip2 \{\} \;

es decir, si el directorio donde están los archivos que desea comprimir es /var/log/blah, sería:

find /var/log/blah -not -name \*.bz2 -exec bzip2 \{\} \;