Couple of comments here that deserve saying:
1) The key reason for this behavior has nothing to do with PowerShell, per se. It has to do TOTALLY with the way Export-mailbox works. Rather than operating iteratively on each pipeline entry, Export-Mailbox works just like Move-Mailbox... it collects all of the pipeline inputs (in ProcessRecord) and then waits until all inputs are collected before taking any action (in EndProcess). This is done so that it can run multi-threaded. If it had to deal with each iteration in ProcessRecord, it would not be able to process multiple exports simultaneously. This is why it "takes a while to start", since it has to accumulate all of the entries into Export-mailbox before it can start.
Ok, that said, it leads into point #2:
2) Get-Mailbox doesn't have to collect all of the result objects before it passes any of them along on the pipeline. The comments about being limited by the way AD works *ARE* true... but the result set that is treated monolithicly is the AD page size (generally 1000 objects), not the full set of objects. This means if you say "-ResultSize:Unlimited" it won't have to collect tens of thousands of objects, potentially, before any are streamed into the pipeline. Rather, it will send the first 1000 as a block, etc.
So, the reason why we get the 'faster' behavior from a ForEach(-Object) loop here is that the Export-Mailbox isn't blocked on executing until 1000 objects are received -- it only has to wait for one object; not because the Get-Mailbox is blocked until all of the (>1000) objects are returned from AD.