Dave - i think what you need here is some basic Exchange knowledge.
Exchange stores mail information at a high level in "Storage Groups".
Each SG may have a number of "Stores".
One of the SGs will also have the Public Folders - just another Store.
Each store is a DATABASE - 2 files, really - *.stm & *.edb.
The public folder store will be the same.
Corresponding to each STORAGE GROUP (NOT STORE) is a set of transaction logs.
(If you're careful not to delete anything, you can use Explorer on your Exchange server and find all this)
When you use the "Information Store" selection, you are backing up these raw database files, as one large file, and, if you set the option, flushing the transaction logs.
You DO NOT use the AOFO for this - you are NOT backing up EACH MESSAGE as an individual file. You are backup up the databases as a whole, the that's the purpose of the Agent for Exchange.
This type of backup happens quickly, and is the one you need to do a full Exchange environment restore in case of disaster.
Do it FIRST, do it to it's own backup job, get it over and done with. SAFE.
Whe you use the "Exchange Mailboxes" selection, you are backing up each individual mail message as a separate virtual file. This takes much much longer.
But, it lets you, in the restore tab, drill down to an individual user's mail items and restore as appropriate.
If you have the time, and your backup media has the capacity, you could run a second backup job to the same media as the "Information Store" backup and APPEND the mailbox backup.
There really is lots and lots of info about this in the Backup Exec help file. With this basic knowledge of the Exchange structure, I'm sure you'll be able to work your way through it.
hope this helps.