I'm not entirely sure why this is, but if you loop through all of the messages in a mailbox, calling imap_header() each time, you can significantly increase performance by calling imap_headers() first.
Compare this:
<?php
     $imap = imap_open("{my.server.com:143}INBOX", "user", "pass");
     $n_msgs = imap_num_msg($imap);
     $s = microtime(true);
     for ($i=0; $i<$n_msgs; $i++) {
          $header = imap_header($imap, $i);
     }
     $e = microtime(true);
     echo ($e - $s);
     imap_close($imap);
?>
With this:
<?php
     $imap = imap_open("{my.server.com:143}INBOX", "user", "pass");
     $n_msgs = imap_num_msg($imap);
  imap_headers($imap)
  $s = microtime(true);
     for ($i=0; $i<$n_msgs; $i++) {
          $header = imap_header($imap, $i);
     }
     $e = microtime(true);
     echo ($e - $s);
     imap_close($imap);
?>
The performance difference, as I have tested on several boxes, connecting to several different servers, is that the second code snippet ALWAYS takes 1/2 the time, if not less.
Perhaps it is because imap_headers() retrieves all of the messages on one connection, whereas imap_header() has to make a new fetch request for each message??  I'm not sure WHY it is faster if imap_headers() is called first, but I do know that it is, so I thought I'd pass on the knowledge.  If anyone knows why this is, please let me know....