[List.asmx web reference].Lists mylistService = new [List.asmx web reference].Lists();
XPathNavigator nav = this.CreateNavigator();

// Get Column Values
string strField1 = (string)nav.SelectSingleNode("[xPath to field1]", this.NamespaceManager).ValueAs(typeof(string));
string strField2 = (string)nav.SelectSingleNode("[xPath to field2]", this.NamespaceManager).ValueAs(typeof(string));
string strField3 = (string)nav.SelectSingleNode("[xPath to field3]", this.NamespaceManager).ValueAs(typeof(string));

XmlDocument xmlDoc = new System.Xml.XmlDocument();
XmlElement elBatch = xmlDoc.CreateElement("Batch");
XmlElement xnQuery = xmlDoc.CreateElement("Query");

string strID;
mylistService.Credentials = System.Net.CredentialCache.DefaultCredentials;

//Build CAML Query
xnQuery.InnerXml = "<where><and><and>" +
  "<eq><fieldref name="Field1"><value type="Text">" +
  strField1 + "</value></fieldref>" +
  "<eq><fieldref name="Field2"><value type="Text">" +
  strField2 + "</value></fieldref>" +
  "</eq><eq><fieldref name="Field3"><value type="Text">" +
  strField3 + "</value></fieldref></eq></eq>";</and></and></where>

//Query List
XmlNode xmlList = mylistService.GetListItems("[SharePoinit List Name]", "", xnQuery, null, "20000", null, "");

//Get Item ID
strID = xmlList.InnerXml;
int intStart = strID.IndexOf("ows_ID");
string tmpID = strID.Substring(intStart + 8);
int intEnd = tmpID.IndexOf("ows");
strID = tmpID.Substring(0, intEnd - 2);

//Build Batch Command
string strBatch = "<method id="1" cmd="Delete">" +
  "<field name="ID">" + strID + "</field></method>";
elBatch.SetAttribute("OnError", "Continue");
elBatch.InnerXml = strBatch;
XmlNode ndReturn = mylistService.UpdateListItems("[SharePoint List Name]", elBatch);