PHP 4.0.6
 './configure' '--with-apxs=/usr/local/sbin/apxs' '--with-config-file-path=/usr/local/etc' '--enable-versioning' '--with-system-regex' '--disable-debug' '--enable-track-vars' '--without-gd' '--without-mysql' '--with-gd=/usr/local' '--with-freetype-dir=/usr/local' '--with-jpeg-dir=/usr/local' '--with-png-dir=/usr/local' '--with-zlib' '--with-mcrypt=/usr/local' '--with-mhash=/usr/local' '--with-imap=/usr/local' '--with-mysql=/usr/local' '--with-sybase=/usr/local' '--with-ldap=/usr/local' '--with-xml' '--with-expat-dir=/usr/local' '--with-sablot=/usr/local' '--with-expat-dir=/usr/local' '--enable-ftp' '--with-curl=/usr/local' '--with-gettext=/usr/local' '--with-iconv=/usr/local' '--with-pspell=/usr/local' '--with-ming=/usr/local' '--enable-sockets' '--enable-trans-sid' '--with-iconv=/usr/local' '--prefix=/usr/local' 'i386--freebsd4.4'

imap c-client: version 2001 release candidate 1 (from FreeBSD ports current)

imap server: Courier-IMAP 1.3.12

--------
1. I login using telnet client on port 143 of my IMAP server:
me: a001 LOGIN username password
server: a001 OK LOGIN Ok.
me: a001 SELECT INBOX
sv: a001 (bla lba bla)
sv: ...
sv: a001 OK [READ-WRITE] Ok.
me: a001 SEARCH HEADER "Message-Id" "<200111201443.fAKEh2154079@home.altech.com.pl>"
sv: * SEARCH 1
sv: a001 OK SEARCH done.

As we can see server has found the message (msgno=1)

2. I use PHP script to do exactly the same:
<?php
$imap=imap_open("{localhost:143}INBOX", "username", "password", 0); // this works beacause other imap_ things works (not included)
$a=imap_search($imap, 'HEADER "Message-Id" "<200111201443.fAKEh2154079@home.altech.com.pl>"', SE_UID);
(...)
?>

It does not find the message, however:

$a=imap_search($imap, 'TEXT "<200111201443.fAKEh2154079@home.altech.com.pl>"', SE_UID);

Finds one.

The other search key that did not worked properly from PHP, (but in telnet session worked) is UID