Pretty quick...
That's pretty quick considering the process that the shortcuted items go through in order to be retrieved. Remember to open that item we make a request to temporarily restore the item to the deleted items folder of the end-user, and once we've kicked off that request we then poll that folder for the message being restored there (the polling is at fixed intervals), once it's there we display it.
If I remember correctly the process is the same in OWA 2003 and OWA 2007, though performance is likely to differ
slightly.
Hope that helps,
Working for cloudficient.com