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!