Finally, exchange has major issues responding correctly to imap calls. The get_number_of_message() function in postieIMAP.php doesn't work at all.
I updated this to use
$recent = imap_num_msg($this->_connection);
Though this means deleting messages after they've been processed. Though not ideal it at least returns and processes messages.
Perhaps theres another exchange safe command?