Outlook 2002, Sent messages not actually being sent to ISP

I have a customer who has a strange problem with MS Outlook 2002 (XP). He
has a POP3 Account from their Companies Web Hosting Account (Hosted by
Network Solutions), Periodically his email appears to be sent (Goes from
Outbox to Sent Mail) in MS Outlook, but is never received by his intended
recipients, and NO Error messages show up. He can do a Test Send from the
Configuration part of MS Outlook and that will work. He can do a Pure WEB
based POP3 Email and that works. I've uninstalled and then reinstalled
(rebooted in-between) MS Outlook XP (2002), and then applied all updates, but
that does not clear things up. Other Computers and Users on the same LAN
have no issue sending email. Since I put his PST files on the Server, and
reference them via a users shared drive, I have configured a Terminal Server
Session for his ID to also use that same PST File… From the terminal Server
His ID works Correctly… So, I'm thinking there must be some issue with his
desktop. I've done a recent AV Scan (Symantec 10.x) & SpyWare Scans (SpyBot
S&D and Ad-Aware), Check his LSPs and nothing looks fishy!.