Algorithm to split bipartite graph into subgraphs
It smells like it might be NP-hard.

One plausible approach is to use a SAT solver or ILP solver.  Suppose you decide you want to have at most $m$ subgraphs.  Then you can have boolean variables $x_{i,k},y_{j,k}$ indicating that customer $i$ goes into subgraph $k$ and service $j$ goes into subgraph $k$.  You can obtain a bunch of constraints (clauses) based on your requirements and then ask the SAT solver or ILP solver to find a feasible solution.  The worst-case running time is exponential.  This might or might not work well enough in your situation.