I use both of them. Nagios for service monitoring and status notification. Zabbix for statistics collection, graphs and also for a few notifications. Nagios is initially a bitch to configure for large network and Zabbix was also very confusing at the beginning.
Are you looking to monitor servers that are in multiple physical locations, or are you attempting to monitor servers that are in one spot, but checking from multiple locations?
Both Nagios and Zabbix can be setup to monitor systems in multiple locations, but configuration of everything out of the box in this mode is a bit involved. Of the two, Zabbix probably has better distributed support, although with enough work you can get comparable setups with both.
Correlating results from different monitoring locations to avoid false positives with these systems is harder - you can use something like the Nagios Event Broker to do this, but the configuration of this layer gets harder.
There are a number of monitoring services that take care of outage confirmation before sending alerts, you might want to look into one of those to see if it fits your needs.
I would recommend Zabbix for your requirements, Nagios is a pain to setup in a distributed monitoring scenario. Don't get me wrong I love Nagios and use it thoroughly but if you are looking for redundancy in your monitoring then Zabbix is a better choice.
We had zabbix running side by side with nagios for quite some time but found nagios to be the all around better tool for monitoring hosts and services. Due to the amount of hosts and service checks we decided use cricket and cacti for metrics.
Another solution one of my fellow engineers is looking at is Zenoss which also looks promising.