Other people suggest sending out regular messages saying things are ok, but personally I don't agree with that. Monitoring should be silent unless there's a problem, and should never rely on a user noticing that something is wrong, like "Oh, I haven't gotten that daily e-mail in a few days." Especially if you have more than one person responding to alerts, each may think that the other has already removed the daily "I'm ok" message.
We have an external service (of which there are hundreds, but we use wormly) to do HTTP checks of our monitoring server to make sure that it's up and can reach the Internet. That's our primary concern for monitoring it. Then our Nagios server monitors all of our clients Nagios servers.
But, you bring up a good point. We probably should add an HTTP URL that checks the postfix queue and if it shows unusual number of messages, which probably means it has any in the queue, then raise an alert. Another option would be to use different methods for alerts, say a non-SMTP SMS delivery agent as well as SMTP that we currently use.
In our case though, I can't recall that we've ever had the mail server die. Of course, all that mail server is used for is sending Nagios alerts, so the configuration is very simple and almost never changes.