Mail.app: weird, huge numbers of messages in title bar, Time Machine quit working
I remember solving an issue similar to this, one or two years ago. I don't have a Snow Leopard system handy so unfortunately I cannot be absolutely sure as to the process required. The steps below are what I would do for a Lion system with some notes attached where possible adaptations would be required.

As you suspected, the problem is due to a file becoming corrupt.

Solution:


Quit Mail if it is open.
In Finder, go to ~/Library/Mail and backup the folder contents
While still in ~/Library/Mail, open the subfolder called V2. Inside that folder there should be a folder called MailData, open that folder.
(If you do not see a folder called V2 or a folder called MailData, it is because the folder structure may have changed between OS versions. Proceed to step four in this case.)
There are a few possible files which may need to be removed from the User's mail folder. In the MailData folder (or if you do not have a MailData folder) search for and move the following files to the Desktop:


(I suggest removing them one at a time and relaunching Mail after removing each file. If it works, your job is done.)


DefaultCounts
LSMMap2
Envelope Index   --  (If you have to delete this file, delete the following two at the same time)
Envelope Index-shm
Envelope Index-wal


A possible pitfall to this method: There is a possibility all messages in folders could get marked as Unread. Depending on the users workflow, this could also be a problem; though a solvable problem through sorting read and unread messages temporarily into different folders and recombining later.