Are you tied to Net::SMTP? I've had pretty good experience with Mail::Send, as well as other modules in that suite, like Mail::Mailer. Although, I'm guessing your smtp server requires authentication, so have you tried running it with the debug option? This is from the Net::SMTP docs:

    $smtp = Net::SMTP->new('mailhost',
                           Hello => 'my.mail.domain'
                           Timeout => 30,
                           Debug   => 1,
                          );
[download]

Also, I'd think you could try telnetting to the mailhost on port 25, and seeing if it responds properly.