I think Thunderbird is great for searching. I have an "All Mail" Search Folder saved on which I use the Quick Filter to find any message I want. Convenient, quick and bug free (in my experience). Can't vouch for it never missing an email, but I've always found what I needed.

If all you have is Bugzilla, everything looks like a bug.

That would be a good start. Then all you'd have to do is get them to understand the difference between a database and a network.