Please try using this CVS snapshot:

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

CVS snapshot results in same error :
ext/openssl/.libs/openssl.o(.text+0xd83): In function `zm_startup_openssl':
/root/php5-200506141430/ext/openssl/openssl.c:589: undefined reference to `OPENSSL_add_all_algorithms_noconf'
/usr/local/ssl/lib/libssl.a(s2_srvr.o)(.text+0x1644): In function `request_certificate':
: undefined reference to `EVP_MD_CTX_init'
/usr/local/ssl/lib/libssl.a(s2_srvr.o)(.text+0x165c): In function `request_certificate':
: undefined reference to `EVP_DigestInit_ex'
/usr/local/ssl/lib/libssl.a(s2_srvr.o)(.text+0x174c): In function `request_certificate':
: undefined reference to `EVP_MD_CTX_cleanup'
/usr/local/ssl/lib/libssl.a(s2_clnt.o)(.text+0x1228): In function `client_certificate':
: undefined reference to `EVP_MD_CTX_init'
....
collect2: ld returned 1 exit status
make: *** [sapi/cli/php] Error 1

Are you sure you really removed ALL existing old Openssl headers?? Please try this:

# find / -name 'evp.h'

The result :
/root>find / -name 'evp.h'
/root/install/openssl-0.9.7g/crypto/evp/evp.h
/root/install/openssl-0.9.7g/include/openssl/evp.h
/root/install/openssl-0.9.7d/crypto/evp/evp.h
/root/install/openssl-0.9.7d/include/openssl/evp.h
/usr/local/ssl/include/openssl/evp.h
/root>

You compiled Openssl yourself? Can you please try using the precompiled packages?

And remove EVERY instance of openssl first from your machine!
(including sources)

I can's possibly use packages in OpenSSL due to company policy (we are not allowed to use certain encryption techniques for level reasons). I don't see the point in doing so, as I'm compiling PHP from source as well. The system is clean of any OpenSSL remains (check every file in the OpenSSL package, removed them all).
Anything else you can suggest to further debug things ?

Please provide the configure line you used for openssl.
This works fine as long as your headers and libraries match..

Configure line :
./config no-mdc2

But I just tried with just ./config and it results in the same thing.

I tried myself, installed openssl with the default stuff and compiled php with it (I have now 2 versions installed) and it works just fine. 

Try this:
# rm config.cache && ./configure --disable-all --disable-cgi --with-openssl=/usr/local/ssl/ 
# make clean && make

Exactly WHAT Redhat you have? (version)

RedHat 7.2, but very well updated.

Anyway, --disable-all and --disable-cgi seems to work.
Also, "configure --with-openssl=/usr/local/ssl --disable-all" works fine. But when I remove the --disable-all, I get the same problems. Any suggestions on how to narrow it down without having to go through each single option ?

What if you started with telling what the full configure line is you use?

./configure  --with-openssl=/usr/local/ssl --disable-all already makes it fail.

My normal ./configure is :
 ./configure  --with-apxs=/usr/local/apache/bin/apxs --with-imap --with-mysql=/usr/local/mysql --with-openssl=/usr/local/ssl --with-pear --with-mcrypt --with-pcre
--with-zlib --with-gd --enable-exif --with-pdflib=/usr/local --with-curl --with-dom=/usr/local --with-qtdom

Now you say it didn't work?! You propably just didn't do "rm -f config.cache && make clean" between tests..

Now, try without --with-imap and --with-curl first.
(both c-client and curl libraries/headers might contain SSL related stuff, you need to recompile those too using the new openssl!)

I removed the PHP source directory and did :
 ./configure \
--with-apxs=/usr/local/apache/bin/apxs \
--with-openssl=/usr/local/ssl

Same error.

Does this work:

# ./configure --disable-all \
--with-apxs=/usr/local/apache/bin/apxs \
--with-openssl=/usr/local/ssl

??

That works perfectly.

Then add the other options one by one (KEEP the --disable-all in there!) and see which causes the error.

Small update : if I don't add --enable-libxml, it seems to work just fine. I have libXML 2.6.8

Please DO NOT add such huge configure outputs here unless asked for! I deleted the comment as it didn't hold any useful information anyway.

1. Send me the Makefile's of configure without --enable-libxml and with it to sniper@php.net

2. What does this output:
# xml2-config --libs --cflags

Output of xml2-config --libs --cflags :
-L/usr/local/lib -lxml2 -lz -lpthread -lm
-I/usr/local/include/libxml2

Makefiles have been sent to you.

And you're absolutely sure there aren't ANY other OpenSSL header files anywhere in your system? Are you able to reproduce this on any other machine??

There are no other SSL files on the system. I've removed every instance of every file that was either installed using 'make install' or was in the package.

Can you or can you not reproduce this on any other machines?

This is the only machine with this specific configuration. The other machines are running Debian. The only one running a webserver there, doesn't even run PHP.

Basically, this machine is the only one running PHP on Linux.

As soon as someone else can reproduce this, I will reopen and look into this issue.

Apparently nobody else has had this problem -> user error -> bogus.