To me, the difference seems about whether you make an effort of doing something, or whether you make an effort in order to achieve something. The latter goes with "um ... zu".
(1) Er hat sich alle Mühe gegeben, es sie glauben zu lassen.
(2) Er hat sich alle Mühe gegeben, um es sie glauben zu lassen.
Both wordings are possible, though there is a difference in what they literally express. The first one expresses that he made all efforts to make her believe (i.e., he made only those efforts that are suited to make her believe). The second one expresses that he made all efforts (no restriction), and did that with the aim of making her believe. The difference may be rather nuanced and tends to be overheard, but it would explain why the first sentence is more natural.
It also explains the possibility of reordering. While this one is possible (though a bit construed, because "Mühe (ge)geben" belong together):
(1') Er hat sich alle Mühe, es sie glauben zu lassen, gegeben.
this one is awkward:
(2') *Er hat sich alle Mühe, um es sie glauben zu lassen, gegeben.
Again, let's compare:
(3) Deshalb haben wir doch diese ganze Mühe auf uns genommen, es zu bekommen.
(4) Deshalb haben wir doch diese ganze Mühe auf uns genommen, um es zu bekommen.
Sentence (3) expresses that this is why we made all the efforts of getting X. This requires that the reason (what "Deshalb" refers to) has already been mentioned or is contextually salient.
Sentence (4) expresses that we made all those efforts ("diese ganze Mühe"), and we did it in order to get X. This requires that the efforts have already been mentioned or are contextually salient. It does not require that any reason has been mentioned yet, because the sentence is giving a reason ("Deshalb ..., um ... zu ...")
Hence, I think that depending on the context, both sentences are possible. That said, I find the reordered
(3') Deshalb haben wir doch diese ganze Mühe, es zu bekommen, auf uns genommen.
more natural than (3). "aus uns genommen" seems a bit wide a stretch in this case...