I just ran across a very strange behavior that I figured I'd better blog about, in case it might help someone else. I'm not yet sure what the problem is, but I found the solution.
I was configuring a machine for demonstration purposes that had Outlook 2007 running on a Windows Server 2008 domain controller/DNS server (again this was just for demo purposes) that has an SMTP server running on it. Outlook would not connect to POP3, SMTP or IMAP when I used the DNS name of the server. I had to use the IP address. This is despite the fact that DNS is configured perfectly and there are no other IP or DNS related problems on the machine. Again, I'm not sure why this is happening, but the fix was just to configure the mail account in Outlook with an IP address.