Here's some more data. The first page of the crash dump. The corroborating evidence is the fact that there is addressbook related stuff on the top of the stack:
Process: Mail 
Version: 6.0 (1485)
Build Info: Mail-1485000000000000~3
Code Type: X86-64 (Native)
Parent Process: launchd 
User ID: 509
Date/Time: 2012-07-31 10:32:23.189 -0700
OS Version: Mac OS X 10.8 (12A269)
Report Version: 10
Sleep/Wake UUID: 92628109-2395-4759-921D-5FF92910E305
Crashed Thread: 0 Dispatch queue: com.apple.main-thread
Exception Type: EXC_BAD_ACCESS (SIGSEGV)
Exception Codes: KERN_INVALID_ADDRESS at 0x0000000000000000
VM Regions Near 0:
__TEXT 0000000104197000-0000000104534000 [ 3700K] r-x/rwx SM=COW /Applications/Mail.app/Contents/MacOS/Mail
Thread 0 Crashed:: Dispatch queue: com.apple.main-thread
0 libsystem_c.dylib 0x00007fff8f449690 strlen + 16
1 com.apple.AddressBook.framework 0x00007fff91767f58 ABInitFileLock + 34
2 com.apple.AddressBook.framework 0x00007fff9176474c -[ABAddressBook nts_InitDefaultContactManager] + 250
3 com.apple.AddressBook.framework 0x00007fff9176452c +[ABAddressBook nts_SharedAddressBook] + 82
4 com.apple.AddressBook.framework 0x00007fff9176443b +[ABAddressBook nts_CreateSharedAddressBook] + 49
5 com.apple.AddressBook.framework 0x00007fff91763788 +[ABAddressBook sharedAddressBook] + 69
6 com.apple.AddressBook.framework 0x00007fff91785a01 +[ABAddressBook addressBookWithDatabaseDirectory:options:] + 60
7 com.apple.MessageFramework 0x00007fff8b9cdd5a +[MailAccount _setMailAccounts:calledFromSync:reloadingFromPreferences:] + 2595
8 com.apple.MessageFramework 0x00007fff8b9c9184 +[MailAccount reloadMailAccounts] + 61
9 com.apple.MessageFramework 0x00007fff8b9c9132 +[MailAccount _mailAccountsIncludingUnknownTypes] + 29
10 com.apple.MessageFramework 0x00007fff8b9c9056 +[MailAccount mailAccounts] + 61
11 com.apple.MessageFramework 0x00007fff8b9d014f +[MailAccount haveAccountsBeenConfigured] + 47
12 com.apple.mail 0x000000010419ae58 0x104197000 + 15960
13 com.apple.CoreFoundation 0x00007fff85971b8a _CFXNotificationPost + 2554
14 com.apple.Foundation 0x00007fff8a781a76 -[NSNotificationCenter postNotificationName:object:userInfo:] + 64
15 com.apple.mail 0x00000001041997d5 0x104197000 + 10197
16 com.apple.AppKit 0x00007fff8e933f5d -[NSApplication _postDidFinishNotification] + 292
17 com.apple.AppKit 0x00007fff8e933c96 -[NSApplication _sendFinishLaunchingNotification] + 216
18 com.apple.AppKit 0x00007fff8e930ec2 -[NSApplication(NSAppleEventHandling) _handleAEOpenEvent:] + 566
19 com.apple.AppKit 0x00007fff8e930abc -[NSApplication(NSAppleEventHandling) _handleCoreEvent:withReplyEvent:] + 351
20 com.apple.Foundation 0x00007fff8a79b35b -[NSAppleEventManager dispatchRawAppleEvent:withRawReply:handlerRefCon:] + 308
21 com.apple.Foundation 0x00007fff8a79b1bd _NSAppleEventManagerGenericHandler + 106
22 com.apple.AE 0x00007fff887f8f68 aeDispatchAppleEvent(AEDesc const*, AEDesc*, unsigned int, unsigned char*) + 307
23 com.apple.AE 0x00007fff887f8dc9 dispatchEventAndSendReply(AEDesc const*, AEDesc*) + 37
24 com.apple.AE 0x00007fff887f8c89 aeProcessAppleEvent + 318
25 com.apple.HIToolbox 0x00007fff8ae69e29 AEProcessAppleEvent + 100
26 com.apple.AppKit 0x00007fff8e92d2a6 _DPSNextEvent + 1456
27 com.apple.AppKit 0x00007fff8e92c862 -[NSApplication nextEventMatchingMask:untilDate:inMode:dequeue:] + 128
28 com.apple.AppKit 0x00007fff8e923c03 -[NSApplication run] + 517
29 com.apple.AppKit 0x00007fff8e8c8656 NSApplicationMain + 869
30 libdyld.dylib 0x00007fff91cb27e1 start + 1
My mail started crashing after 2 days of running fine as well. One one of my users, the program won't open at all and on the other, it will open but then crash in about a minute or two. I think it all started happening right after I started messing with messages.
I'm wondering if your app stays open long enough for you to open window/previous recipients to see if it is empty like mine. I also notice that there is no auto suggestion on addresses in mail.
I do have addresses in my address book but mail just isn't seeing them or storing new recipients.
I have tried all fixes mentioned for mail, messages, address book, and previous contacts. Nothing worked. I even reinstalled ML and that didn't help. I also spent about 2 hours on the phone with Apple. The guy who was helping me said it was the first issue with mail he knew about. Nothing that we tried helped.
I wasn't able to set icloud mail back up through the icloud panel BUT when starting mail I was able to add the iCloud email and it set itself up normally. Then when checking the iCloud control panel, mail sync was on and working fine. So this is a fix but one of last resort as it does delete your mail accounts.
@Sanjaya @Daniel @Happy
I had the same problem and I managed to fix my problem. I put my info here :-
But basically I just moved the following directory to a backup and let Mail recreate a new one. Please be aware that this fix just refeshes your Mail, i.e. you'll need to readd your accounts and if you pop your mail, then I'm not certain if you can re-import them back in :-
More specifically it was the following file (or some other file in the same directory?) that mattered :-
/Users/sean/Library/Containers/com.apple.mail/Data/Library/Saved Application State/com.apple.mail.savedState/data.data
Maybe if you want to try to save your popped mail, you could try just moving the com.apple.mail.savedState away and leave the parent directory alone?
Anyhow, give this a shot to see if it works.
You're the man! I renamed ~/Library/Containers/com.apple.mail and started Mail -- no more crashes! It rebuilt everything and now my Mail app is working again! Thanks.
 I didn't even have a file ~/Library/Containers/com.apple.mail/Data/Library/Saved Application State/com.apple.mail.savedState/data.data so I just went to the top level directory (com.apple.mail) and renamed that.
 I didn't lose any data -- Mail rebuilt it from my emails although I did notice that the directory ~/Library/Containers/com.apple.mail/Data/Library/Mail Downloads no longer exists. So I don't quite know where Mail relocated the attached files, but I checked and I can access them by searching.
I was reconciled to waiting for a Mountain Lion update before I could start using Mail again, but thanks to you I am now back in business.
I echo Sanjaya's remarks, notes, and applaud. You sir, are the man! I tried the saved states deletion, but found that it didn't do anything, but remove the first dialog message (before the crash log). I went back to ~/Library/Containers/com.apple.mail/ and moved the contents to the trash (but not emptied). Opened Mail and everything was there, even the last message I had left open behind the viewer. I didn't have to re-add anything, just had to reinstate my view preferences; akin to flashing the PRAM.
Thanks again Sean! Without your help, I wouldn't have ventured down that path. It's fixed!
I read through several threads before I found this one. My machine does NOT have ~/Library/Containers/...
Here is what I have done, and so far - Mail has stabalized and is working again!
I went to ~/Library/Mail/V2/[insert name of account here]
Each of my accounts, three Gmail and one Mac account all conatined three hidden files:
.dat45ab.nnn ( the nnn were different on each account
I shut down Mail and made a "keep" folder and omved all three files in each of the four accounts into the "keep" folder. Re-started Mail and have been stable for over two hours now (earlier today, I lost track of how many times Mail crashed).
@macfrompc: Thanks very much for this tip! I had tried deleteing other things like the Saved Application State folder, but wasn't having any luck and was about to nuke everything and start from scratch. Before doing that I tried your tip and deleted the hidden files in each mail account folder. Now Mail is behaving itself again, and I am a happy guy!