This all true and it's why I didn't go with my original suggestion which was to use SNMP or WMI or whatever to monitor uptime. I haven't used Munin so I can't really comment on that but we've use Nagios for monitoring and alerting for years and it will do exactly what you've identified in your third paragraph. Nagios will give you system availability for your hosts (servers) and the services that run on them. So you can, for example, see that the server has had 100% availability in the past 3 months but the IMAP daemon has just 99.75%.
Depending on your requirements, of course, you could/should run both Munin and Nagios since they both serve different needs with some small overlap (Munin is probably a bit closer in functionality to MRTG, Cricket or Cacti).
Oh, one last thing - regardless of which combination you go for, the likelihood is that you're going to have a bit of work to do each month or each quarter when it comes to taking the data in Munin or Nagios and presenting it in a report of some sort. Again, not overly familiar with Munin but Nagios is ancient and it shows both in the presentation of its Web UI and the backend that it uses for storing data.