Are there any nagios plugins or tools for viewing performance reports in a cool way

As you stated, because Exchange uses the store.exe process for all mailbox databases, it is not possible to monitor individual mailbox database that way. There may be ways to do so by talking directley to Exchange, but I don't know of any process for Nagios that can do that.

The store.exe process is the Exchange Information Store service, this can be monitored by Nagios. If the mailbox databases dismounts because of diskspace issues, and many other issues it is likely this server will have stopped as well. Monitoring this should give you a good indication of mailbox issues

This article is an excellent tutorial on setting up monitoring for Exchange services and includes a lot of info on the different things you can check to monitor your Exchange servers health.

[Edit]

Windows Performance Counters does have a counter for the Exchange store, the MSExchangeIS Mailbox, counter so this may also be able to be used.

Ok I finally got it working.

The problem was that both nagios servers are performing service checks and reporting results to master node, and all those check were performed perfectly. Master node had service freshness checking so if the monitoring servers could not complete checks master server would scheduled those checks from itself.

Anyways, new servers were on new ip range and by default nrpe port was closed on master server.

Opening the port solved the problem. Although it's still odd that it returned "Service check timed out" instead of "Socket timeout error".