I think you are right, it's harder than I thought.

The problem can in fact be modeled with a graph in which you need to find vertex-disjoint paths between pairs of vertices (s1,t1), (s2,t2), and so on, but this problem seems not to be reducible to max-flow, instead it is NP-hard.