Momentan läuft's auf einer modifizierten Version von Xardas' Query.
Code (SQL): 
SELECT
                customer_id,
                date,
                (
                    SELECT      COUNT(date)
                    FROM        invoices
                    WHERE       invoices.customer_id = contracts.customer_id
                    AND         DATE_FORMAT(invoices.date, '%Y%m') = DATE_FORMAT(dates.date, '%Y%m')
                    GROUP BY    date
                ) > 0 AS has_invoice
    FROM
                contracts
    INNER JOIN
                dates ON (
                    dates.date >= delivery_date AND (
                        termination_date IS NULL OR dates.date <= termination_date
                ))
    WHERE date <= NOW()
Ich werde' mir das später noch mal ansehen, ob es sich nicht noch optimieren läßt, aber für's Erste läuft es und ich habe dringendere Probleme (sprich: Wartung unseres nagelneuen Legacy-Systems).