If you using 2010 or later then you can use the Conversation operations in EWS to do that see http://msdn.microsoft.com/en-us/library/office/dn610351(v=exchg.150).aspx
Another method you can use is Grab the Transport Headers from the extedned property and parse out the InReplyTo header eg
ItemView view = new ItemView(100);
view.PropertySet = new PropertySet(PropertySet.IdOnly);
PropertySet PropSet = new PropertySet();
PropSet.Add(ItemSchema.HasAttachments);
PropSet.Add(ItemSchema.Body);
PropSet.Add(ItemSchema.DisplayTo);
PropSet.Add(ItemSchema.IsDraft);
PropSet.Add(ItemSchema.DateTimeCreated);
PropSet.Add(ItemSchema.DateTimeReceived);
ExtendedPropertyDefinition PR_TRANSPORT_MESSAGE_HEADERS = new ExtendedPropertyDefinition(0x007D, MapiPropertyType.String);
PropSet.Add(PR_TRANSPORT_MESSAGE_HEADERS);
FindItemsResults<Item> findResults;
List<EmailMessage> emails = new List<EmailMessage>();
do
{
findResults = service.FindItems(WellKnownFolderName.Inbox, view);
if (findResults.Items.Count > 0)
{
service.LoadPropertiesForItems(findResults.Items, PropSet);
foreach (var item in findResults.Items)
{
String Headers = "";
if (item.TryGetProperty(PR_TRANSPORT_MESSAGE_HEADERS, out Headers))
{
Int32 slen = Headers.IndexOf("In-Reply-To:");
if (slen > 0)
{
Int32 elen = Headers.IndexOf("\r\n", (slen + 12));
Console.WriteLine("InReponse to : " + Headers.Substring((slen+12),elen-(slen+12)));
}
}
}
}
view.Offset += findResults.Items.Count;
} while (findResults.MoreAvailable);
Cheers
Glen