私はSUM-CASEアプローチを好みます:
SELECT x.name
FROM
(SELECT c.name, SUM(CASE WHEN b.paid_out THEN 0 ELSE 1 END) all_paid
FROM customers c JOIN living_places l ON c.ID = l.ID
JOIN policies p ON l.code = p.code_living_place
JOIN bills b ON p.code_policy = b.code_policy
GROUP BY c.name) x
WHERE x.all_paid = 0;
ここでもHAVING句を使用することで、ネストされたSELECTを回避できるかもしれません...