Outlook 2000 Connecting through port 25

I have a problem with Microsoft Outlook connecting through port 25 of the SMTP server provided by our ISP. Apparently, when attempting to send emails I get the message “System Undeliverable no transport provider was available for delivery to this recipient”. We are able to send emails via Outlook Express and we are also able to Telnet into the SMTP server. It is only when we attempt to send via Outlook that we experience this problem. It’s like Outlook is experiencing timeout problems or something. This is happening with most of the PC’s on the network. Are there any suggestions out there?