Besides the usual environmental questions (how many Exchange servers, what version of OS/Exchange, etc.), I'd want to know approximately how many messages there are, the number of mailboxes that contain messages to be imported, and the size of each mailbox. This should be readily available through the System Manager (if 2003) or Exchange Console (if 2007+).
As for technique, it really depends on how many mailboxes and the budget:
If there's < 10 users and there's not much of a budget to do this, you could setup an open source DoveCot IMAP server on their premises (or remotely) and walk them through adding an IMAP account to each of their Outlook profiles and simply drag and drop the messages into the IMAP account; IMAP stores it's messages in several optional ways on the filesystem, is fairly well-documented, and (as you say) would "not be a problem" to import files into your application.
If there's a lot of mailboxes (and likely a larger budget), I'd use EXMERGE to bulk export .PSTs for each mailbox and you could use Zimbra's PST Import Wizard to import all their mail into a Zimbra server which I believe stores mail on the filesystem or MySQL (need to double-check that, but likely something doable).
there's also quite a few options in 3rd-party commercial or open source PST-to-$someFormatorMediaryFormat tools, some require alot or a little code to write.
The good news is, this isn't as exotic as a request as you may think right now; there's alot of Exchange alternatives out there that need to have a reliable method of importing data from Exchange or nobody would convert.
I'd favor going a well-documented route like IMAP/Maildir/MIME Format: once you get it into that format reliably, there's likely alot of open source parse tools in your language of choice to help you import it into your application.
Regardless of what you choose, I would do a "slice" first: decide what's doable, grab a sample set of data from the client to do a test run (or if that doesn't fly, get a good idea of what kind of documents they're storing, whether in sub-folders or not, what kind of "metadata" they use to organize the messages, and create your own sample set) and then extrapolate the time it'll take you to do all of it, padding it accordingly depending on your comfort level.