Search across all mailboxes in domain?

Is this possible:

I want 5 mailboxes for 5 users in 1 domain. I want to have access to search for emails and document attachments across the domain. I need to be able to search and view each users accounts. Is this possible?

I ask because we all support our clients and any of us could email them. WHen they call in for support, we need to be able to see who last emailed the client and about what.

Is this cross-mailbox within a domain search possible?