Since I prefer to use Evolution, I would really like to completely remove Thunderbird from my PC. I already performed
sudo apt-get purge thunderbird* but
locate thunderbird still lists some hits! How can I completely remove it?
Here is what went wrong in your case.
There are two ways using which you can remove Mozilla Thunderbird from your Ubuntu system installation, without affecting other applications.
Both these methods have been explained in detail at my blog - http://terminaltwister.com/remove-mozilla-thunderbird-email-client-from-ubuntu-13-04/
Have a look it it for detailed steps with screen-shots.
Chose any one of these methods and Thunderbird will be removed successfully from your system.