I have posted about this in the past - and others have posted as well. I am running a small IMAP server with a couple of accounts on it. I have everything forwarded in the router and working fine - most of the time. However, periodically (seems like every couple of days) it stops working. I can telnet to the port inside of the network just fine, use the external address and it fails. Then, it will just start working again. So if telnet works internally and not externally this means that either the router is not working or something in the verizon network? However, other ports work just fine while port 143 is not working. Does anyone else have this issue and if so what have the done about it? Thanks.
Might see if there is a firmware update that stabilizes that router. Are you using only the Verizon Provided one, or do you have a couple routers?
It's also possible that the router is going bad would be one of my first impressions (as long as everything looked fine in the software firewall's) Don't trust that they are ok, double check them, as firewall rules change or can change.
As you go through the FAQ - you'll see that Verizon doesn't intentionally block that port, however there may be a software firewall that is going cookoo, or the router itself is starting to go bad. If you haven't already done so, double check your software firewalls and make sure your program/server and port are given full access and are showing as "allow"