Statement 1:
Nach meinem Umzug musste ich mich überall ummelden. Das war anstrengend.
Statement 2:
Es war anstrengend, dass nach meinem Umzug ich mich überall ummelden musste.
or can statement 2 be also replaced with:
Es war anstrengend, dass nach meinem Umzug umzumelden.
On a similar note:
Man darf nicht ohne Visum in die USA einreisen. Das ist verboten.
and
Es ist verboten, in die USA ohne Visum einzureisen.
To my understanding, statement 2 puts more emphasis on "es war anstrengend"; the subordinate clause is mainly an explanation what was exhausting.
In statement 1, both sentences have the same emphasis.
Your alternative is not correct:
Es war anstrengend,
dass nach meinem Umzug umzumelden.
You could use:
Es war anstrengend, mich nach meinem Umzug überall umzumelden.
In your second example, a changed order sounds/looks more natural to me, probably because "ohne Visum" is the most important part.
Es ist verboten, ohne Visum in die USA einzureisen.
