After your main loop possibly just do another loop to go from 1 - $max_id and tar up then rm -rf each lower numbered directory?
Maybe I'm missing something but it seems like you're 99% there.
Make sure you make a complete backup of your directory before testing anything that deletes files. Make sure the tar files contain the files you think they do. Make sure the right directories are deleted.