After spending some time figuring out what the different flag field values represent, it seems that bit 8 determines whether or not the mail is deleted. So I determined which mails in the database have this bit set with the following query:
select * from mail_item where (flags & 128) ;
It returned all of the mail that was not showing up in that folder. Then a simple:
update mail_item set flags = flags - 128 where (flags & 128)
and poof all the mail is back.
From what I've read on the forums here, it's not recommended to modify the database directly. So if you find yourself in this situation, be sure you know what you're doing. I don't know Zimbra very well, but I have gotten the results I need with this method. I've made my choice and now I'm going to stick with it.
Oh and just for reference, other flags. And please take this with a grain of salt, because I'm not a Zimbra developer and I'm sure there is a header file somewhere that has all this stuff laid out for fact. Or, at least I hope so.
1 - 00000001 - Sent
2 - 00000010 -Read
4 - 00000100 - Replied
8 - 00001000 - Forwarded
16 - 00010000 - dunno
32 - 00100000 - Flagged
64 - 01000000 - Draft
128 - 10000000 - Deleted
I stopped there.