Haven't heard this about Thunderbird 3, lots of moans about the
automatic settings wizard that kicks in when installed but not
freezing when getting mail.

You've tried removing TB3 but did you do it through Synaptic where you
have the option for complete removal ( i.e. all configuration files
relating to it too ).

After that, all I can suggest it trying another e-mail client and
seeing if that does the same - if so then the problem is in the e-mail
service itself or some setting it doesn't like.

Have you double checked all the settings compared to what is expected
by the provider ?