Is sampling a valid way to reduce complexity?
I would get a sufficiently large random/representative sample and cluster that.
To see what is such a sample, you will have to get two such samples and cluster them to get cluster solutions c1 and c2. If the matching clusters of c1 and c2 have the same model parameters, then you probably have representative samples.
You can match the clusters by looking at how c1 and c2 assign drawn data to clusters.