You mentioned being confused by the large number of mail parsing modules available. For maximum compatability I would advise using the Mail::Cclient module from CPAN as it is just a thin perl wrapper around the exact same C library pine uses to parse mail.

Although it is most likely pine is using mbox folders, there is a possibility it could be one of the several other formats c-client supports which are also stored as flat files.

Also I have used Mail::Box and it is quite fast. It is however IIRC pure perl so there is a chance that Mail::Cclient being based on C is faster. But I haven't done any benchmarks.