OK - well this certainly doesn't sound like an errant mouseclick issue anymore. Sounds like something in Mail.app definitely got hosed. I would try a couple of things at this juncture:
First, would be to run Disk Utility and repair permissions, followed by verify disk. If errors found, you should run Disk Utility from booting up from the Installer DVD, and selecting Disk Utility from the Utilities menu once you've progressed far enough to get a menu bar across the top of your screen, and run "repair disk." If there were any "file system was modified" messages, rerun over and over until you don't get those messages anymore.
Alternatively, you could reboot while holding the ⌘s keys. This brings you up into what is known as single-user mode -- a unix command window. Once you have the login prompt, type
fsck -fy⏎. If there were any "file system was modified" messages, rerun over and over until you don't get those messages anymore. Once complete, type
exit⏎ to reboot normally.
Then, I would reapply the OS 10.6.4 combo update. You can get it at
http://support.apple.com/kb/dl1048. Some recommend (and probably even have an Apple reference to justify it) running Disk Utility repair permissions again. Follow that by an online software update to pick up any subsequently released security patches and other fixes.
If you still have issues after all that, you could try reinstalling the Mail.app. It's on your Installation DVD in the "Optional Installs" folder -- there are a number of user-selectable applications inside that installer. Then, it's the combo update and online software update routine again. But, a reinstall of Mail.app should most definitely get all the icons back. I'd want to do all the verify disk stuff first, though, just to make sure it is being reinstalled on a disk that is in tip-top shape.