Is set packing easier when the sets are squares?
I think your problem is NP-complete already for M=3, as there is a quite straight-forward reduction to it from 3SAT. Just for each variable xi, make a pair of squares, truei and falsei. For a clause Cj, make a pair of squares for each of its literals, e.g., Aj1, Bj1, Aj2, Bj2, Aj3, Bj3. Let Aj1 intersect the respective square of the variable (e.g., truei) (but disjoint from any other similar clause-squares intersecting it), while the Bj1, Bj2 and Bj3 are put somewhere in a disjoint way. Finally, for each clause we have a collection of three squares, which is also Bj1, Bj2 and Bj3.