We've got two Nagios servers: one that I set up on a box in the local office and one that existed prior to my employment that is on a machine about at thousand miles away (literally, it's on the other side of the country).
Anywhos, this older Nagios box (running ver 2.0bv3, I believe), will often randomly have critical services with that error, while our local Nagios box reports no problems. We've discovered that the issue is a POS ISP that this box is running on. Not sure if that could be your problem, since 1.3 is a stable release and that'd be an error I'd expect from a Beta version.
But to stop the notifications, I'd take Luca's advice: increase the amount of retries before the notification is sent out.