We are currently having ~100 servers and all of them are using remote syslog, so we have aggregated all logs on one server.
The most questioned problem from our support team is: Has an email from .... to ... been delivered?
I'd like to give to our support team access to some logging tool and some guide for searching in logs. What would you have recommended me? Or, do you know any other alternatives to test?
The problem of grepping logs is that there is not sender and recipient address on one line. So I supposed, there might by some aggregation by email id.
Logstach and graylog are probably good tools to solve you problem. But you could maybe take a look at rsyslogd. You can use it to specify logs templates, selector and filters, and take different actions based on that. For example, when log line matches the first filter regexp it can trigger an insert in an SQL DB or a document addition in any kind of index based on your template and you're output module. And the second template can trigger an update of the SQL row or the indexed document. Although this is not a ready to use solution, this is quire simple to setup and can make searches a lot easier.
If interested take a look at the pages bellow:
http://www.rsyslog.com/doc/rsyslog_conf_filter.html
http://www.rsyslog.com/doc/rainerscript.html
General tip: A web UI for your central log server should help, then the task requires maybe two searches (one for the recepient address and one for the queue ID to see the whole process). See https://serverfault.com/a/591857/29023
If you are talking about a big mailserver then an appliance like Mailtrace might be the right solution. (Website is german only, but it does exactly this: provide a helpdesk UI to correlated mail logs.)