The Perl for System Administration book (available here) has some examples in chapter 8. You might download the example code.

The author also suggests the Win32::MAPI module to make things easier, if you can't use Win32::OLE.

If I were in your situation, I'd try PSA example code first. It doesn't look too tough.