If you know ID only, you can get ChangeKey easily, for example for folder:
private FolderIdType GetFullFolderID(string folderID)
{
GetFolderType request = new GetFolderType();
request.FolderIds = new BaseFolderIdType[1];
FolderIdType id = new FolderIdType();
id.Id = folderID;
request.FolderIds[0] = id;
request.FolderShape = new FolderResponseShapeType();
request.FolderShape.BaseShape = DefaultShapeNamesType.IdOnly;
GetFolderResponseType response = _binding.GetFolder(request);
FailOnError(response);
FolderInfoResponseMessageType firmt = (FolderInfoResponseMessageType)response.ResponseMessages.Items[0];
FolderType ft = (FolderType)firmt.Folders[0];
id.ChangeKey = ft.FolderId.ChangeKey;
return id;
}