Updated and resolved for my situation:
I called MS Premier and this is now resolved for my issue with a workaround. The technician is going to submit a bug fix but basically he found another bug ticket from summer 2009 that stated "if the mailbox has more than 49 proxy addresses entered within
the Email addresses tab the search command will fail".
We re-tested a few failed search mailboxes by removing unnecessary proxy addresses from that tab the searches worked fine.
Hope this helps others.
Mike
This resolved the issue I was having as well - the recipient I was trying to track for had a ton of extra smtp addresses that were not needed. Removing them fixed the issue.
There is an amazing pack of free network admin tools.
click here to download it