Yes, we receive a host down notification as well, but it doesn't necessarily come before the service notifications.
e.g. recently when a server was rebooted, we saw this sequence of e-mail alerts:
** PROBLEM: servername CPU Load is CRITICAL **
** PROBLEM: servername NSClient++ Version is CRITICAL **
** PROBLEM: servername Uptime is CRITICAL **
** PROBLEM Host Alert: servername is DOWN **
** RECOVERY Host Alert: servername is UP **
** RECOVERY: servername CPU Load is OK **
** RECOVERY: servername NSClient++ Version is OK **
** RECOVERY: servername Uptime is OK **
Of course, each of those "critical" service alerts was really a "Socket timeout after 10 seconds" error because the host had already gone down. We did not receive alerts for drive space or memory usage, which indicates that Nagios did stop alerting for services after the host-down message went out.
I thought I had read in the documentation that Nagios would check the host status before sending a service alert, but it appears that this isn't happening. Is there anything we can do? Does the maximum number of attempts for the host have to be smaller than for each service, in order for the host to go DOWN before any services go CRITICAL?