In your figure, for large trees it seems that the minimum is very close to the maximum, which can also mean that the distance you are using is not very discriminative.
My guess is that you are using the RF distance – and two random trees rarely have bipartitions in common, which explains the large RF. If that is what you want (no bipartitions in common), then you are fine. However there are other ways of defining “very different trees”: for instance if you move just one leave from one end to another of the tree, this will result in a large RF distance but the trees are still very similar in terms of the SPR distance or their maximum agreement subtree (MAST).
(I like Brian’s idea, BTW!)