Thanks to Claus Ibsen for such a helpful response to my previous post. As Claus points out, the answer is to use a Camel helper class, PredicateBuilder, which contains a bunch of useful static combinator methods. Claus shows in his post how to implement my trivial conjunction easily using the and() method. Note the generic signatures of all these helper methods, e.g.
<E extends Exchange> Predicate<E> and(final Predicate<E> left, final Predicate<E> right)
Because they accept Exchange (or any derived class), any custom Predicate you might need to write has access to the complete message exchange structure (in, out and fault), and all predicates could be applied to a custom extension of Exchange.
Having got over those two 'humps' (sorry - couldn't resist that), I'm feeling very good about Camel. It's a mighty impressive piece of work and looks like it has a lot of potential for the area I'm working in right now.