Even contacts that have been accidentally deleted can be recovered (as long as those contacts had been sync'ed). So if a contact has been "seen" by the service (after capturing was enabled), then it is safely stored and available for download.
Capturing can is optional, and for existing Premium Service users must be enabled on the account settings page:

The device status page shows if your device's contacts have been captured:

Contact data can be viewed, and a snapshot taken of the current contacts state via the device management page:

Here's an example after contacts have been syncing and 4 contacts deleted. All the contacts, included the deleted ones can be downloaded from this page:

This example shows a snapshot (the lower table row) and the changes since the snapshot was taken. A snapshot allows recovery of contact data from the past even if the contacts have since been changed.

More information about this feature can be found on this page.