Automatic detection of interface implementations for query operators - is a difficult topic, primarily because it's hard to get right with good performance. Currently, the re-linq front-end is quite fast because it only does dictionary lookups for the MethodInfos coming in via MethodCallExpressions (plus GetBaseMethod() and GetGenericTypeDefinition()/GetGenericMethodDefinition()). With interface method implementations, this is not that simple - we can't perform dictionary lookups, which are O(1) operations (leaving the calls mentioned above aside); we have to get an interface map for the registered interfaces and perform a linear search through the "TargetMethods" array of that interface map. This makes the lookup an O(N*M) operation, where N is the number of registered interface types, and M is the number of methods in those interfaces.
We could try to make it perform better by detecting interface methods by name first, and only then check the interface map, but it would still be much slower than an ordinary lookup - and you must not forget that re-linq has to perform that lookup for every MethodCallExpression in an expression tree in order to detect whether a method call refers to a query operator or not. So this has to be really fast.
This means we would definitely need to perform some kind of caching, which we've been able to avoid before. We'd have to expose control over the cache's lifetime to the user of re-linq (ie., the LINQ provider), and so on.