There is an even newer patch available for Settlers IV. The patch has number 872 and is supposed to remove all the freezes. (Yeah right).
Unfortunately I have not seen a "fixed" patch in GCW for us who wishes to make backups of the game.
Is anyone working on it?