I spent several months working on trying to solve this problem and after spending a long time working with Microsoft SharePoint and WIF engineers came to the conclusion that this is not possible. It appears that the issue is basically what Kirk alludes to. When creating an impersonated session using Claims (e.g. creating an SPClaim and converting into a SPUser), SharePoint is not actually creating a completely impersonated session. The session that is created is really only understood by the object model. That means that when you step outside of the boundary of the web application and into search you are effectively performing a double hop because you stepping into another application domain/process space.
I tried to do something similar to what eppesuig suggests and could not get it to work. Perhaps if you wrote a whole new STS that could generate a trusted claim token that SharePoint would accept then you might be able to work around this using the ActAs token (SharePoint absolutely will not accept the OnBehalfOf token). However, the security implications of doing that are rather concerning. Theoretically it should work but getting the custom STS and SharePoint to intermingle/trust proved to be outside of my ability. I would love to see someone else try it, though.