If you need to go with the web service, you will probably have to go with SPQueries (CAML) to get the items you want.
The Lists.asmx web service (located under http://sitecollection/_vti_bin/Lists.asmx) has a function called GetListItem that takes a Query as a parameter.
I don't really know the inner workings of your list, but something like this query should do it :
XmlDocument camlDocument = new XmlDocument();
XmlNode queryNode = camlDocument.CreateElement("Query");
queryNode.InnerXml = "<Where>"
+ "<Eq><FieldRef Name='FileName' /><Value Type='Text'>{Your Filename Here}</Value></Eq>"
+ "</Where>";
XmlNode viewFieldsNode = camlDocument.CreateElement("ViewFields");
viewFieldsNode.InnerXml = "<FieldRef Name='ID' />";
XmlNode queryOptionsNode = camlDocument.CreateElement("QueryOptions");
resultNode = _sharepointSite.ListsWS.GetListItems(listName, viewName,
queryNode, viewFieldsNode, rowLimit, queryOptionsNode, webID);
The _sharepointSite and ListWS objects are your web serivce objects (they should be generated automatically for you when you add your web reference).
The listName is the name of your list on the site collection
The viewName is the name of the view you want to query on (make sure you have a view that shows all elements if you want to query on everything. I usually rely on hidden views to make sure that users don't change them)
RowLimit is just an int.
You should have no problem finding the ID of the web you are working on with the web service.
The XML that you will get back is not that straight forward and will need special attention. More informat
Note that if you are dealing with nested folders, you will want to add the following code :
XmlNode queryOptionsNode = camlDocument.CreateElement("QueryOptions");
queryOptionsNode.InnerXml = "<ViewAttributes Scope=\"Recursive\" />";
More information on what I explained here.