[SalesForce] Deploy list views of classes, pages, etc

UPDATE: 11th Nov, I discovered the WorkflowRule (as apposed to the Workflow) metadata type! Combined with the ValidationRule metadata type. This means that the Metadata listMetadata API call now returns exactly the two lists you need to implement your search tool.

This will allow you to list the Validation Rules and Workflow Rules from Apex.

MetadataService.MetadataPort service = MetadataServiceExamples.createService();     
List<MetadataService.ListMetadataQuery> queries = new List<MetadataService.ListMetadataQuery>();        
MetadataService.ListMetadataQuery queryWorkflow = new MetadataService.ListMetadataQuery();
queryWorkflow.type_x = 'WorkflowRule';
queries.add(queryWorkflow);     
MetadataService.ListMetadataQuery queryValidationRule = new MetadataService.ListMetadataQuery();
queryValidationRule.type_x = 'ValidationRule';
queries.add(queryValidationRule);           
MetadataService.FileProperties[] fileProperties = service.listMetadata(queries, 25);
for(MetadataService.FileProperties fileProperty : fileProperties)
    System.debug(fileProperty.fullName);

For more information and the MetadataService and MetadataServiceExamples class used in the above code. Please take a look at this Github repo and Readme file.

It turns out the following DeployOptions setting was what I was missing:

singlePackage
boolean
Indicates whether the specified .zip file points to a directory structure with a single package (true) or a set of packages (false).

I needed to set this to true, as I assume my flat zip file represents a single package. After doing that the Number of Components Deployed became 1 and the custom object moved into Deleted Objects (as I hadn't checked purgeOnDelete).