Ive seen the same thing in 7.2. with no database failover or database replication.
Just like the OP says, the log says that there are no contacts for the alarm but of course that isnt true. Every once in a while the system that I was administering would have a database fault, everything would recover fine but I never could pin down if the two were related.
We ended up setting up an alarm that would email out every 30 minutes and then we setup a system that would check the inbox and verify that the alarm emails would make it in, if not it would notify us. I think instead of restarting the system, all I would do is just go to the alert notification profile config on the webpage and save it, and then everything would work correctly again.