Ordering on two criteria ?
SELECT DISTINCT * FROM table ORDER BY paid, client_id
Problem is, you will have something like this :
+------------+-----------+
| paid | client_id |
+------------+-----------+
| 2006-07-01 | 00001 |
| 2006-07-10 | 00005 |
| 2006-07-10 | 00009 |
| 2006-07-31 | 00017 |
| 2006-08-02 | 00025 |
| 2006-08-11 | 00035 |
| 2006-08-25 | 00100 |
| 2006-08-31 | 00123 |
| | 00002 |
| | 00003 |
| | 00004 |
| | 00005 |
| | 00006 |
| | 00008 |
+------------+-----------+
So people without 'paid' value will not be in random order.
Or may be split the problem into two smaller SQL query ?
SELECT DISTINCT * FROM table ORDER BY paid, client_id WHERE (paid != "")
SELECT DISTINCT * FROM table WHERE (paid = "") ORDER BY rand()