What does this output for you ?
<?php
var_dump(mail());
?>

And make sure that sendmail headers were found during ./configure execution (check `./configure ..... | grep -i sendmail`).

it finds sendmail in /usr/lib/sendmail and the dump_var(mail()); returns NULL

and in main/php_config.h HAVE_SENDMAIL is ... ?

#define HAVE_SENDMAIL 1

Then I don't see how it could happen that in mail.c HAVE_SENDMAIL is 0.
Please try fresh snapshot from http://snaps.php.net and if it doesn't work too - try to investigate why HAVE_SENDMAIL in mail.c is zero, while in included file it's 1.

I've defined HAVE_SENDMAIL 1 in mail.c just to be sure
and it seems it is ok:
$ strings .libs/libphp4.so|grep mail
mail
mb_send_mail
mb_orig_mail
mail
vpopmail.directory
called mail() function.
sendmail_path
Permission denied: unable to execute shell to run mail delivery binary '%s'
Could not execute mail delivery program '%s'
Path to sendmail
sendmail_from
sendmail_path
/usr/lib/sendmail -t -i

Please try using this CVS snapshot:

  http://snaps.php.net/php4-STABLE-latest.tar.gz
 
For Windows:
 
  http://snaps.php.net/win32/php4-win32-STABLE-latest.zip

same with the snapshot.

That's interesting.
From what I can see, mail.c includes php.h, which includes tsrm_virtual_cwd.h, which includes tsrm_config_common.h, which includes tsrm_config.h, which in turn includes php_config.h, where HAVE_SENDMAIL is defined.

I.e. it looks like this:
mail.c
 php.h
  tsrm_config.h
   tsrm_config_common.h
    tsrm_config.h
     php_config.h 

Could you plz figure out which one of these includes doesn't get included and why?

As i told you i've added #define HAVE_SENDMAIL 1 to
mail.c just after the includes and before the #ifded HAVE_SENDMAIL. And as you can see strings shows that the functions are compiled in. I doubt that this is a header problem, because they get compiled in w/o my define too.

>As i told you i've added #define HAVE_SENDMAIL 1 to
>mail.c just after the includes and before the #ifded
> HAVE_SENDMAIL

Right. And this should have caused warning saying that "HAVE_SENDMAIL" have been redefined (as it does for me).
That's why I assume that it was never defined before because php_config.h didn't get included.
That's pretty weird behaviour and I haven't heard about anyone who is able to reproduce it.

I've defined HAVE_SENDMAIL in CFLAGS just to be sure it gets defined everywhere, but of course i still have the same issue.

That's not what I asked you to do.

tsrm_config.h is missing.

It doesn't exist at all or it's just empty?
Could you provide access to this machine?

Sorry. I fucked it. It exists and includes #include <../main/php_config.h>. No sorry i can't give access to the machine.

Ok, we're back again to the question: what is missing? 

It seems nothing is missing. I am relly courious what could be the problem. It is just wo wierd. You can check phpinfo() here: http://users.silihost.hu/phpinfo.php
Maybe you will catch something.

You really need to have sendmail (or something compatible) installed. It won't magically just work otherwise..

Have you even read the comments? PHP does not even try to execute the given sendmail binary.