You should be able to manually add an application to your firewall, which you don't mention, nor do you say what OS you are using ?
But even with it deleted I would have though it would be recreated if you start Thunderbird, though the fact that it would be redirected through the mail shield proxy (which may be the problem), your firewall (?) may not even know thunderbird is involved. But I'm guessing that you may be using avast! Internet Security, since it is the only avast product with a firewall, as you talk about "I assumed that, on rebooting, avast! would pick it up again and add it to the rules list."
Try stopping the Mail Shield for 10 minutes, then start Thunderbird and send yourself a test email, that should have your firewall ask permission.