I just joined Verizon yesterday. I already have Outlook for my email - NOT Express. I am having difficulty getting it set up to send and receive email. I have already changed to pop.verizon.net and smpt.verizon.net.
A lot of Verizon's e-mail accounts are hosted with AOL. Some may also be hosted on Yahoo. You'll want to make sure that Outlook is set to use the secure ports, not the default, unsecure ports.
I would recommend the use of IMAP, by the way. This way your e-mail account reflects on mobile devices and webmail too. POP should only be used if you have no intention of checking e-mail from anywhere but Outlook.