The date format for e.g. SINCE is, according to rfc3501:

date            = date-text / DQUOTE date-text DQUOTE

date-day        = 1*2DIGIT
                    ; Day of month

date-day-fixed  = (SP DIGIT) / 2DIGIT
                    ; Fixed-format version of date-day

date-month      = "Jan" / "Feb" / "Mar" / "Apr" / "May" / "Jun" /
                  "Jul" / "Aug" / "Sep" / "Oct" / "Nov" / "Dec"

date-text       = date-day "-" date-month "-" date-year

So a valid date is e.g. "22-Jul-2012" with or without the double quotes.

It has been noted that imap_search breaks with imap4 syntax.  To do an imap 4 search use curl and send a custom command, then grab the results.  Its best to do a UID search to get the unique IDs to work with later.  Here's an example with a working curl function.

<?php
$host = 'your-server.tld';
$user = 'username';
$pass = 'password';
$folder = 'INBOX';

function send_imap_command($server, $user, $pass, $command, $folder="INBOX")
{   //Send an imap command directly to the imap server

    $result=["response"=>"", "error"=>""];
    $url = "imaps://$server/". rawurlencode($folder);
    $options=[CURLOPT_URL=>$url, CURLOPT_PORT=> 993, CURLOPT_USERNAME=> $user,
        CURLOPT_PASSWORD=> $pass, CURLOPT_RETURNTRANSFER=> true, CURLOPT_HEADER=> true,
        CURLOPT_CUSTOMREQUEST=> $command];
    $ch = curl_init();
    curl_setopt_array($ch, $options);

    $result["response"] = curl_exec($ch);
    if(curl_errno($ch)) $response["error"]="Error (". curl_errno($ch) ."): ". curl_error($ch);

    return $result;
}

//Pull out all the emails returned as undeliverable by the remote mail server in the inbox using curl
$response=send_imap_command($host, $user, $pass,
            'UID SEARCH SINCE "01-Jan-2022" (OR FROM "mailer-daemon" FROM "postmaster") (OR SUBJECT "fail" (OR SUBJECT "undeliver" SUBJECT "returned"))',
            $folder);

if($response["error"]!="")
{
    echo $response["error"]."\n";
} elseif (strlen($response["response"])>5){
    //Server returns a string in the form * SEARCH uid1 uid2 uid3 ...  Clean up and create array of UIDs.
    $response["response"]=str_replace("* SEARCH ","",$response["response"]);
    $messages=explode(" ",$response["response"]);
}

print_r($messages);
?>

Hi, 
be aware, that imap_search() does NOT (as you may exspect) return an empty array, if nothing was found! 
As the manual says, it returns FALSE.

Do not test the result like "count($array)" as I did. 
This gives you 1 for an empty result. Took me an hour to found out why :-(  RTFM

imap_search function is not fully compatible with IMAP4. the c-client used as of now supports only IMAP2 and some search criterion will not be available for use such as "OR"

So a php code similar to:
$inbox   = imap_open('{imap.example.com:993/imap/ssl}INBOX', '[email protected]', 'pass123', OP_READONLY);
$search_string = 'SUBJECT "FedEx" OR SUBJECT "USPS"';    
$emails = imap_search($inbox, $search_string);

will throw an error saying "Unknown search criterion"

observations and reference:

PHP source trace:(ref: https://github.com/php/php-src/blob/master/ext/imap/php_imap.c)
    /ext/imap/php_imap.c -> line no : 4126
    imap_search => line no : 4148

c-client library source trace:
src/c-client/mail.c -> line no : 3973

internal.txt -> line no : 1919 => mail_criteria()
    criteria IMAP2-format search criteria string
    WARNING: This function does not accept IMAP4 search criteria.

IMAP2 RFC1064 => [ref: https://tools.ietf.org/html/rfc1064] [page: 13]
IMAP4 RFC2060 => [ref: http://www.faqs.org/rfcs/rfc2060.html] [section: 6.4.4]

Note:
The core search functionality in a core module(IMAP) is still not available in PHP. Hope this will be brought to the developer community's attention...

To set your own CHARSET, which is useful if you are dealing with Chinese Japanese and Korean queries.

<?php imap_search($inbox,'BODY "'.$keyword.'"', SE_FREE, "UTF-8"); ?>

Please be aware about UID of the message.
It is NOT an ID that never change!

If you move your message to another folder in your IMAP account, this UID WILL CHANGE. 

So if your message has UID = 100 (in INBOX folder) and you move it to some subfolder and then back to INBOX, it's new UID in INBOX will be 101.

This is the correct way to use the imap_search with ON "date"

$date = date("j F Y");

$emails = imap_search($inbox,'ON "'.$date.'"' );

imap_search() always returns false when op_silent flag is set in the connection parameters.