How to use CopyIntoItems to copy files into existing doclib items

This is my scenario: I need to copy files to a sharepoint document library using its web services and set metadata on them. That's all possible with CopyIntoItems (from Copy webservice) except for Lookup fields. CopyIntoItems ignores them, so i need another way to set data on those fields.

I've tried to create a list item with the mandatory and lookup fields metadata and then, using the item ID (creating a FieldInformation field with the ID, as well as some other simple metadata), called the CopyIntoItems method and, instead of updating the item, sharepoint created a new one.

I can't do this in the reverse order because i have no way to get the ID from the item created by CopyIntoItems...

So, the question is: How can i upload a file to a sharepoint document library and set all its metadata? Including Lookup fields.

1. Use a regular PUT WebRequest to to upload the document into the library
2. Query the document library to find the ID of the item you just uploaded (based on path)
3. Use the Lists.asmx web service to update the document metadata

Helpful link: Uploading files to the SharePoint Document Library and updating any metadata columns