Efficient querying of Child Elements?

We are trying to implement an inhouse backup of our CRMoD data and cannot find a way to effectively query for Modified Child elements - such as Contact/Account Addresses, and can find no documentation on this.

With Contacts for example, trying to get daily deltas of modified addresses by (in effect) looping through a million Contacts is surely not the way to go?

There is an inconsistancy (in our implementation) of what happens to the Parent Object <modifiedDate> element when the Address is modified. Where the Address is embedded in the Parent Object, and it is updated by editing that Parent object, then the Parent Object Modifed tag is updated. Where it is not edited from within the Parent Object (even if embedded) or where additional addresses (not in the Parent Object) are modified, then the Parent object <modifiedDate> tag is not updated.