I have found a solution that is very very satisfactory.
I looked through the complicated code of the pagination functionality and found, logically, that paginate sets conditions and passes these to a find function of the model (unless the model has it's own 'paginate' function).
I first tried overriding the paginate function, but this was too complicated. The solution I found in the end is to pass on joins to the paginate's options just like you would pass them when doing 'find' on a model:
//Set the pagination options:
`$this->paginate = array(
'limit' => 25,
'order' => array(
'Customer.lastname1' => 'asc'
),
'joins' =>
array(
// OUTER JOIN because I wanted to also
// fetch record that do not have a 'contact'
array(
'table' => 'contacts',
'alias' => 'Contact',
'type' => 'LEFT OUTER',
'conditions' => array(
'Customer.id = Contact.customer_id',
'Contact.class' => 'ContactAddress'
)
),
array(
'table' => 'contact_addresses',
'alias' => 'ContactAddress',
'type' => 'LEFT OUTER',
'conditions' => array(
'Contact.index = ContactAddress.id',
)
),
),
// In your conditions you can now use any table that
// was joined as well as the original 'customer' table.
'conditions' => $conditions,
);
$this->set('customers',$this->paginate('Customer'));
Either way I hope this helps someone!