We were migrating a MOSS site collection in production and these servers have anti-virus protection in place. This protection was preventing MOSS-WSS to send outgoing e-mail. The error reported was "Cannot connect to SMTP host " followed by an encrypted server name that was looking like Chinese characters.
To fix the problem, just look at your anti-virus settings to allow SMTP on port 25 and this should work. Thanks to John Powell for the tip.