So I am wondering how I can (cheaply) get a redundant availability monitoring system in place--Is is as simple as running Nagios or Zenoss (or whatever) on two different HyperV hosts?
Sim.
Redundância significa ter mais de um componente crítico. O monitoramento é um componente crítico, portanto, você precisa de mais de um host de monitoramento. Para resolver o problema imediato que você mencionou na sua pergunta, você só precisa configurar um segundo canário em um host separado.
(Observe que não precisa ser uma duplicata completa de seu ambiente de monitoramento se a continuidade no monitoramento não for crítica para você: pode ser apenas uma verificação de nagios ou similar para garantir que o host principal esteja ativo e em execução) .
Soluções mais complexas incluem monitoramento de failover, e você também pode querer considerar um monitor externo (há muitos serviços como Pingdom que ofereça isso) para monitorar seus sistemas mais críticos voltados para o cliente também, mas impressões de primeira vista são de que ambos são excessivos para o que você quer - você só precisa saber se o seu sistema de monitoramento morreu.