Ok, I have discovered the answer to this, thanks in part to @mwrichardsone who prompted me to explore how the Dynamics Crm Linq query provider does it, I was then able to work backwards from there..
So here is the equivalent Linq query expression which works (I am using the CrmOrganisationServiceContext):-
var contactsQuery = from c in orgService.CreateQuery("contact")
join a in orgService.CreateQuery("customeraddress") on (Guid)c["contactid"] equals (Guid)a["parentid"]
where (((string)c["firstname"] == "Max" && (string)c["lastname"] == "Planck")
|| ((string)c["firstname"] == "Albert" && (string)c["lastname"] == "Einstein"))
|| (string)a["line1"] == "The secret moonbase"
select c;
I then found this article which explains how you can convert linq query to a Query Expression or Fetch Xml: http://pogo69.wordpress.com/2012/04/05/crm-linq-provider-converting-expressions-to-queryexpression-andor-fetchxml/
Once i applied that technique I was able to see what the equivalent QueryExpression looks like.. and basically, the bit that I was missing (key insight) is that when you add a ConditionExpression you can set it's "EntityName". This means you can add a ConditionExpression to a filter group thats on the parent / main entity, even though the condition is actually for an attribute thats present on a link entity (in this case customeraddrress line1). I was assuming you had to add the condition to the linkentity that had that particular attribute - which is also what @Henk van Boeijen did in his answer - and that did not give the correct results.
So the final working QueryExpression looks like this (notice the condition for address line 1 is not added to the address link entity, its added to the filter group on the main entity, and it has an "entity name" set to the alias of the link entity)
var orgService = serviceProvider.GetOrganisationService();
using (orgService as IDisposable)
{
var query = new QueryExpression("contact");
query.ColumnSet.AddColumn("firstname");
query.ColumnSet.AddColumn("lastname");
// so link in customer address.
query.AddLink("customeraddress", "contactid", "parentid", JoinOperator.Inner);
var addressLink = query.LinkEntities[0];
addressLink.EntityAlias = "A";
addressLink.IncludeAllColumns();
// conditions for max planck
var firstName1Condition = new ConditionExpression("firstname", ConditionOperator.Equal, "Max");
var lastname1Condition = new ConditionExpression("lastname", ConditionOperator.Equal, "Planck");
// Groups those conditions using an "AND" conjunction.
var maxPlankFilter = new FilterExpression(LogicalOperator.And);
maxPlankFilter.AddCondition(firstName1Condition);
maxPlankFilter.AddCondition(lastname1Condition);
// conditions for albert einstein
var firstname2Condition = new ConditionExpression("firstname", ConditionOperator.Equal, "Albert");
var lastname2Condition = new ConditionExpression("lastname", ConditionOperator.Equal, "Einstein");
// Groups those conditions using an "AND" conjunction.
var albertEinsteinFilter = new FilterExpression(LogicalOperator.And);
albertEinsteinFilter.AddCondition(firstname2Condition);
albertEinsteinFilter.AddCondition(lastname2Condition);
// could optionally chain the 2 filters so we get Albert's contitions chained (using AND) to max's conditions
// albertEinsteinFilter.AddFilter(maxPlankFilter);
// conditions for address line 1 moonbase
var addressLine1Filter = new FilterExpression(LogicalOperator.And);
var line1Condition = new ConditionExpression("A", "line1", ConditionOperator.Equal, "The secret moonbase");
addressLine1Filter.AddCondition(line1Condition);
// add filters to query
// ensures each filter that we add to our queries criteria is chained together using an OR.
query.Criteria.FilterOperator = LogicalOperator.Or;
query.Criteria.AddFilter(albertEinsteinFilter);
query.Criteria.AddFilter(maxPlankFilter);
query.Criteria.AddFilter(addressLine1Filter);
var results = orgService.RetrieveMultiple(query);
int resultCount = 0;
foreach (var r in results.Entities)
{
resultCount++;
Console.WriteLine(string.Format("{0} {1} {2}", (string)r["firstname"], (string)r["lastname"], (string)((AliasedValue)r["A.line1"]).Value));
}
Console.WriteLine("There were " + resultCount + " results..");
}
Side Note: See @Henk van Boeijen's post below if you would like to see a shorter syntax for building a query expression. If productivity is truly your concern however, I would have to echo the comment from @Nicknow below and suggest that you seriously take a look at using the Linq query mechanism for performing CRM queries.
Also @Henk van Boeijen has pointed out that my answer is based on a feature that only appears in the 2013 SDK, and doesn't appear to be in prior versions. I haven't checked this personally, but that information is probably very useful for you to know especially if you are not using the latest versions of the SDK.