The GetListItemChanges response contains *two* <rs:data> elements. E.g. :
<listitems ... >
<rs:data ItemCount="2">
<z:row ... />
<z:row ... />
</rs:data>
<rs:data ItemCount="5">
<z:row ... />
<z:row ... />
<z:row ... />
<z:row ... />
<z:row ... />
</rs:data>
</listitems>
+ The first <rs:data> contains the items that have changed since the 'since' parameter date. The second is only relevant if any items have been deleted since that date.
+ If the second <rs:data> is empty then no items have been deleted. If it contains <z:row> elements then these indicate the IDs of all items that still exist in the list. By implication, any items that don't appear in this list have been deleted and if you are maintaining a local cache of the SharePoint data you can delete any items from it that don't appear in this <rs:data> element.
(Taken from information in http://msdn2.microsoft.com/en-us/library/aa168130(office.11).aspx, Future Work section)