Most exchange servers offer a pop3 and/or imap interface.

Check if your server supports that, and if yes, use it. That should be easier, and there are more examples around.

BTW did you use the Super Search?

Update: Perl MAPI to access Exchange Server and the followups contain some interesting links.