Virtually all email clients now offer those features, though not all are free. I personally like Mozilla Thunderbird, which has the optional extensions I can install for additional features. Among them the ability to send/receive mail from Hotmail, Yahoo, AOL, and a host of others. The adaptive spam filter is great too. Where with Outlook you continually have to download new definition files, Thunderbird's spam filter learns on its own. Over time, it should be able to reach efficacy levels exceeding 90%.
Verizon almost certainly just uses a standard POP3 email system like virtually every other ISP except MSN and AOL. POP3 support is essentially a given in any email program.
Of course Thunderbird isn't the only option out there. Take a look around and see what else there is. Maybe something will work better for your particular needs.
And given that someone erroneously lead you to believe it was a bad idea to install service packs, I'll just include my usual list of tips for keeping a smooth running system.
TIPS FOR A SMOOTH RUNNING SYSTEM
The more of these suggestions you follow, the fewer problems you should have. Follow them all, and you've probably eliminated at least 95% of all potential problem sources.
Things you should NOT do
1: Use Internet Explorer (1)
2: Use any browser based on Internet Explorer
3: Use Outlook or Outlook Express
4: Open email attachments you haven't manually scanned with your virus scanner
5: Open email attachments you were not expecting, no matter who they appear to be from
6: Respond to spam messages, including using unsubscribe links
7: Visit questionable websites (e.g. porn, warez, hacking)
8: Poke unnecessary holes in your firewall by clicking "Allow" every time some program requests access to the Internet (2)
9: Click directly on links in email messages
10: Use file sharing or P2P programs
11: Use pirated programs
Things you SHOULD do
1: Use a non-IE or IE based browser (3)
2: Always have an up to date virus scanner running (4)
3: Always have a firewall running (5)
4: Install all the latest security updates (the exception to the no-IE rule)
5: Delete all unsolicited emails containing attachments without reading
6: Manually scan all email attachments with your virus scanner, regardless of whether it's supposed to be done automatically
7: Copy and paste URLs from email messages into your web browser
8: Inspect links copied and pasted into your web browser to ensure they don't seem to contain a second/different address
(1) Sadly sometimes this is unavoidable, so only use IE when the site absolutely will not work with any other browser and you cannot get that information/service anywhere else, and only use IE for that one specific site.
(2) When it doubt over whether or not to allow some program, use Google to find out what it is and whether or not it needs access to the Internet. Otherwise, denying access is the safest course of action, since you can always change the rule later.
(3) On Windows your options include: Mozilla Firefox, Seamonkey, Opera, Flock, and Safari. It doesn't matter which one you pick so much as that you pick one of them and use it over IE.
(4) AVG Free and Avast are available if you need a decent free virus scanner
(5) XP/Vista's firewall is probably good enough for 99% of all Windows users, but other options include ZoneAlarm, Outpost Firewall, and Comodo. If you have a router with a firewall built into it, there is no need for any of the aforementioned firewalls to be running.