Its very strange. Do You use hosting company server (dedicated/shared/etc) or its your own server?
If hosting company, maybe they can give You the path to sendmail?
Also - I would ask on a global joomla forum about that problem, as it is not related with our templete, but with joomla core functions.