I've setup qmail on my server and never had a problem with sending mail.
None of the people, which are using my server, have ever reported a problem with it.
In a correct setup, a symlink is setup to the executable located in the /var/qmail/bin/sendmail
Check with the sysadmin.