I'm afraid the only way is to use CAML query. Even worse, since you don't have a SPSiteDataQuery alternative in Client Object Model, you can't perform cross-site queries, so you have to query each list separately.
Example code for quering a list with SharePoint 2010 Client Object Model:
string siteUrl = "http://MyServer/sites/MySiteCollection";
string listTitle = "your list title here";
string guid = "put-your-guid-here";
ClientContext clientContext = new ClientContext(siteUrl);
Web site = clientContext.Web;
List targetList = site.Lists.GetByTitle(listTitle);
CamlQuery query = new CamlQuery();
query.ViewXml = String.Format("<View><Query><Where><Eq><FieldRef Name='UniqueId'/><Value Type='Guid'>{0}</Value></Contains></Where></Query></View>", guid);
ListItemCollection collListItem = targetList.GetItems(query);
clientContext.Load(collListItem);
clientContext.ExecuteQuery();
bool itemIsFound = (collListItem.Count == 1);
(the code has been tested and works)