You haven't gotten any answers yet so I figured I would try a sub-optimal solution.
I'm not sure that you will be able to do what you need to do with the tool I'm going to propose (and, perhaps you are beyond this possible solution), but have you tried to find the messages of interest using ExMerge?
I've found that ExMerge can track down specific messages and get them for me across multiple mailboxes. It doesn't look like you can get directly to the PR_SEARCH_KEY value, but maybe there is another way to skin this cat.
You can download ExMerge at Microsoft Download for ExMerge .
Also, there are some good high-level details on ExMerge at the Microsoft Exchange Team Blog .