The optimization process and recommendations:

1. Create Optimal Indexes (modified query below): The recommended indexes are an integral part of this optimization effort and should be created before testing the execution duration of the optimized query.
2. Explicitly ORDER BY After GROUP BY (modified query below): By default, the database sorts all 'GROUP BY col1, col2, ...' queries as if you specified 'ORDER BY col1, col2, ...' in the query as well. If a query includes a GROUP BY clause but you want to avoid the overhead of sorting the result, you can suppress sorting by specifying 'ORDER BY NULL'.
3. Replace In Subquery With Correlated Exists (modified query below): In many cases, an EXISTS subquery with a correlated condition will perform better than a non correlated IN subquery.
4. Sort and Limit Before Joining (modified query below): In cases where the joins aren't filtering any rows, it's possible to sort and limit the amount of rows using a subquery in the FROM clause, before applying the joins to all other tables.

Optimal indexes for this query:

ALTER TABLE `address` ADD INDEX `address_idx_city` (`city`);
ALTER TABLE `payment` ADD INDEX `payment_idx_cancel_dat_customer_init` (`cancel_date`,`customer`,`init`);
ALTER TABLE `payment` ADD INDEX `payment_idx_customer` (`customer`);

The optimized query:

SELECT
        COUNT(a0_id) AS sclr0,
        LOWER(a0_city) AS sclr1 
    FROM
        (SELECT
            a0_.id AS a0_id,
            a0_.city AS a0_city 
        FROM
            address a0_ 
        WHERE
            a0_.city IS NOT NULL 
            AND a0_.city <> '' 
        ORDER BY
            NULL LIMIT 5) a0_ 
    INNER JOIN
        customer c1_ 
            ON (
                c1_.customer_address = a0_.a0_id
            ) 
    WHERE
        1 = 1 
        AND 1 = 1 
        AND (
            EXISTS (
                SELECT
                    1 
                FROM
                    payment p2_ 
                WHERE
                    (
                        p2_.init <> 1 
                        AND p2_.unpaid <> 1 
                        AND p2_.cancel_date IS NULL 
                        AND (
                            p2_.value > 0 
                            OR p2_.date BETWEEN '2011-03-23 00:00:00' AND '2011-03-23 23:59:59'
                        ) 
                        AND p2_.customer IS NOT NULL
                    ) 
                    AND (
                        c1_.id = p2_.customer
                    ) 
                GROUP BY
                    p2_.customer 
                ORDER BY
                    NULL
            )
        ) 
    GROUP BY
        sclr1 
    ORDER BY
        NULL LIMIT 5