I also stopped receiving comment notifications a few days ago. This happened out of the blue - I hadn't changed any of my settings and I still have the tick box checked for emails to be sent.
I just contacted my web server and they confirmed that they stopped receiving emails from WordPress a few days ago, which means that the problem is with WordPress and not the server.
There seems to be countless posts on this problem but no real solution? I don't particularly want to install a plug-in to fix the problem. If anyone knows why this problem has occurred and how to resolve it, please let me know!