PLEASE try this under Apache 1.3.27 before we continue hunting ghosts here. 

Can you check what kind of email is causing this?
Headers, etc.

Any kind of email!
A mail with 'a' for subject and 'b' for body, sent from pine on localhost by the local mta is sufficient.

Try this script (after you've replaced the obvious lines with correct ones):

<?php

$sequence = "2,4:6"; // Replace this with the sequence used in IMP

$mbox = imap_open("{your.imap.host:143}","username","password")
     or die("can't connect: ".imap_last_error());
 
$overview = imap_fetch_overview($mbox,$sequence,0);
 
if(is_array($overview)) {
        reset($overview);
        while( list($key,$val) = each($overview)) {
                print     $val->msgno
                . " - " . $val->date
                . " - " . $val->subject
                . "\n";
        }
}
 
imap_close($mbox);

?>

Posted 2 messages to the mailbox, setted $sequence to "1,2": here is the backtrace:

#0  0x401e0e96 in _php_imap_address_size (addresslist=0x812a160) at /root/temp-apache/php4-STABLE-200307141330/ext/imap/php_imap.c:3643
#1  0x401db8c4 in zif_imap_fetch_overview (ht=3, return_value=0x8126814, this_ptr=0x0, return_value_used=1)
    at /root/temp-apache/php4-STABLE-200307141330/ext/imap/php_imap.c:2722
#2  0x4030c622 in execute (op_array=0x8126014) at /root/temp-apache/php4-STABLE-200307141330/Zend/zend_execute.c:1616
#3  0x402f9494 in zend_execute_scripts (type=8, retval=0x0, file_count=3) at /root/temp-apache/php4-STABLE-200307141330/Zend/zend.c:886
#4  0x402bdfec in php_execute_script (primary_file=0xbffff6c4) at /root/temp-apache/php4-STABLE-200307141330/main/main.c:1685
#5  0x40311cfe in apache_php_module_main (r=0x811d72c, display_source_mode=0)
    at /root/temp-apache/php4-STABLE-200307141330/sapi/apache/sapi_apache.c:54
#6  0x40312dc0 in send_php (r=0x811d72c, display_source_mode=0, filename=0x811e2d4 "/usr/local/apache1.3.27/htdocs/unf.php")
    at /root/temp-apache/php4-STABLE-200307141330/sapi/apache/mod_php4.c:620
#7  0x40312e3f in send_parsed_php (r=0x811d72c) at /root/temp-apache/php4-STABLE-200307141330/sapi/apache/mod_php4.c:635
#8  0x806c0d9 in ap_invoke_handler () at eval.c:88
#9  0x8081c7f in process_request_internal () at eval.c:88
#10 0x8081ce6 in ap_process_request () at eval.c:88
#11 0x8078576 in child_main () at eval.c:88
#12 0x8078731 in make_child () at eval.c:88
#13 0x80788ac in startup_children () at eval.c:88
#14 0x8078f3d in standalone_main () at eval.c:88
#15 0x80797ac in main () at eval.c:88
#16 0x4008d2eb in __libc_start_main (main=0x8079408 <main>, argc=2, ubp_av=0xbffffb04, init=0x804eec8 <_init>, fini=0x80af73c <_fini>, 
    rtld_fini=0x4000c130 <_dl_fini>, stack_end=0xbffffafc) at ../sysdeps/generic/libc-start.c:129

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

No feedback was provided. The bug is being suspended because
we assume that you are no longer experiencing the problem.
If this is not the case and you are able to provide the
information that was requested earlier, please do so and
change the status of the bug back to "Open". Thank you.

i tested the example and imap_fetch_overview crashes in this situation:

php: 4.3.4 with uw imap 2002(e)
imapd: courier-IMAP CAPABILITY IMAP4rev1 CHILDREN NAMESPACE THREAD=ORDEREDSUBJECT THREAD=REFERENCES SORT QUOTA

here not really relevant info:
os: solaris 8/sparc
apache: 1.3.29
uw-imap make: gso SSLTYPE=none
configure-line: ./configure --prefix=/usr/local --with-apxs=/opt/apache/bin/apxs --disable-cgi --disable-debug --with-config-file-path=/usr/local/etc --with-exec-dir --enable-sigchild --disable-magic-quotes --disable-rpath --disable-ipv6 --disable-all --with-openssl --with-zlib --disable-ctype --with-curl --with-gd --with-jpeg-dir=/usr/local --with-png-dir=/usr/local --with-zlib-dir=/usr/local --with-freetype-dir=/usr/local --with-t1lib --enable-gd-native-ttf --with-gettext --with-imap=/path/to/my/uw-imap-2002e --with-ldap --with-mcrypt --with-mysql --with-oci8=/opt/oracle --with-pcre-regex --enable-posix --enable-session --enable-sockets --enable-sysvmsg --enable-sysvsem --enable-sysvshm --enable-xml --with-dom --with-dom-xslt --enable-ftp --enable-mbstring --with-oracle=/opt/oracle --with-expat --enable-shared --enable-static --without-tsrm-threads --enable-cli --without-pear --enable-gcclib

when calling imap_fetch_overview with uid's that are not (by incident) id's too, it crashes.
e.g. imp could cause exactly this problem in imp/mailbox.php : $overview = imap_fetch_overview($imp['stream'], implode(',', $msgs), FT_UID);

when using mmcache, it reports this line in apache error_log and the php crash, followed by the dead apache child info: exit signal Segmentation Fault (11)

using the shared library libc-client.so from sunfreeware, this problem does not exist (but others...)

truss ends up in a long alert(0) followed by this:
    Incurred fault #6, FLTBOUNDS  %pc = 0xFD509B3C
      siginfo: SIGSEGV SEGV_MAPERR addr=0xD8026004
    Received signal #11, SIGSEGV [caught]
      siginfo: SIGSEGV SEGV_MAPERR addr=0xD8026004

Same issue with php 4.3.8 and c-client uw-imap 2004 on redhat enterprise. I think pl101 at clez dot net is right about the cause of the issue.