I found that with Sync Delete selected, every time a Sync was run, one Google contact was deleted. In the end I found the cause. In Syncronizer.LoadGoogleContacts the StartIndex property is assumed to be 0-based when according to Google documentation (http://code.google.com/apis/contacts/docs/2.0/developers_guide_dotnet.html#retrieving_without_query), it's actually 1-based. So the two line that set the StartIndex should be:
query.StartIndex = _googleContacts.Count+1;
Otherwise if you have more than 256 contacts (the NumberToRetrieve), you'll find that the 256th is read twice and as a consequence it's marked for deletion as it appears to be a Google entry that has seen its matching Outlook contact deleted.