There are two parts to this question:
How do I use predicate expressions on navigation properties inside a L2E query?
L2E allows the use of the AsQueryable extension method within a query. This means that I'm able to convert the ICollection to an IQueryable and apply the predicate expression. So far so good. However, it might compile, but it still won't run, since L2E won't know what to do with the predefined expression from the GetComplexPredicate method. This leads us to:
How do I combine several separate predicate expressions into one?
The enormously useful LINQKit can easily combine several predicates into one expression using PredicateBuilder. With the Expand method from LINQKit and the aforementioned AsQueryable, we can finally arrive at a statement that will both compile and run beautifully:
// build the entire predicate beforehand (PredicateBuilder + AsQueryable):
var complexPredicate = GetComplexPredicate();
var condition = PredicateBuilder.True<Customer>()
.And(c => c.Country == "US")
.And(c => c.Invoice.AsQueryable().Any(complexPredicate));
// apply criteria to query (using Expand):
var result = repository.Customer.Where(condition.Expand()).ToList();