The issue is likely caused by a large amount of items in users' calendar folders and mailboxes in general, which Exchange doesn't handle too well.
We hope for performance improvements in Exchange Server 2010, perhaps by using AQS queries.
I've asked a seperate question with further detail.
It seems that the delay wasn't related to the first request in general, but rather the first request that performs a search in a user's mailbox (specifically calendar).
The problem seems to occur only when using SearchFilter/FindItems the first time. Next request flies through without delay.
At first, we suspected the cause being a search on an extended property, but realized that the problem persisted even when searching for calendar items on a specific date instead - i.e. when searching only on first class properties that we would expect to be "indexed" and fast. This is why we hope that AQS and searching on indexed properties in Exchange 2010 may provide the necessary boost in speed.