This pop up warning, is it definitely saying it's blocked OUTGOING data? That's usually a sign that something is trying to 'phone home', or trying to access an external server. Now, without seeing it, I'm only guessing, but it could be Email Notifier that is trying to check your mails, and is being blocked, thus not working. Is Email Notifier in the Program Control list? If so, it should have all green ticks.
What you should be aware of is that if it isn't email notifier, or any other program, or windows application that you know about, it could be a trojan trying to transmit data, which is bad, but not that bad, as ZA has blocked it. The chances are, it's just something you have installed trying to update itself. Firefox checks for updates, so it could even be that, but I would have thought it would have given the program name. Are there no details other than the IP address?
Another thing I thought of today is that when I was trying out all the different security suites, before settling on F-Secure, I found that Zone Alarm Internet Security caused problems with my Mail Washer, which is a similar program to Email Notifier, in that it checks for emails for multiple email accounts, before you actually download them. Email Notifier also checks multiple accounts, and I am wondering if ZA has some sort of general objection to this type of program. I know you said you uninstalled it, and Email Notifier (EMN) still didn't work, but did you reboot after uninstalling ZA? If not, it may have still been blocking access. Can you remember, did EMN work properly before you installed ZA?
Later, when I have more time, I will have a look on the ZA forums, and see if anyone else has posted a similar problem.
Unfortunately, I do suspect a conflict, and you may have to choose another firewall if you want to continue using EMN.