Dunno what to tell you. Perhaps rsync and a dynamic dns approach would be good? IF you want the machines to find each other even through IP changes you need somewhat of them rediscovering each other.

Back up should be a multitiered thing so you don't mind if one goes kaput. That way you can use a 3rd party without 'depending' on them.