Looks like there is something wrong with the Metadata API here.

I did a retrieve for the following package.xml

<?xml version="1.0" encoding="UTF-8"?>
<Package xmlns="http://soap.sforce.com/2006/04/metadata">
    <types>
        <members>*</members>
        <name>FlowDefinition</name>
    </types>
    <version>38.0</version>
</Package>

In my dev org I got a package back with that contained a flowDefinitions for 4 flows.

• flowDefinitions\LeadTest.flowDefinition
• flowDefinitions\New_Customer_Flow.flowDefinition
• flowDefinitions\Test.flowDefinition
• flowDefinitions\UpdateContactAddressFromAccount.flowDefinition

If I try and do a readMetadata using these names I get a Metadata record back for reach flow.

SalesforceSession salesforceSession = \\...
MetadataServiceWrapper metadataService = salesforceSession.GetMetadataService();
SalesforceMetadata.Metadata[] md = metadataService.readMetadata("FlowDefinition", new String[] { "LeadTest", "Test", "LeadTest", "UpdateContactAddressFromAccount"});
foreach (SalesforceMetadata.Metadata m in md)
{
     if(m != null)
     {
          FlowDefinition flow = (FlowDefinition)m;
     }
}

While this returns a Metadata for each requested fullName, there isn't any data in them. Just a null fullName field.

Stepping down a level we can try it with the raw SOAP request

Request

<soapenv:Envelope xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns:met="http://soap.sforce.com/2006/04/metadata">
   <soapenv:Header>
      <met:SessionHeader>
         <met:sessionId>00D700000000001!AQoAQFIx5ZioX_NotARealSessionId_HmH8aIn9Qpw</met:sessionId>
      </met:SessionHeader>
   </soapenv:Header>
   <soapenv:Body>
      <met:readMetadata>
         <met:type>FlowDefinition</met:type>
         <!--Zero or more repetitions:-->
         <met:fullNames>LeadTest</met:fullNames>
         <met:fullNames>Test.flowDefinition</met:fullNames>
      </met:readMetadata>
   </soapenv:Body>
</soapenv:Envelope>

Response

<soapenv:Envelope xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns="http://soap.sforce.com/2006/04/metadata" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
   <soapenv:Body>
      <readMetadataResponse>
         <result>
            <records xsi:nil="true"/>
            <records xsi:nil="true"/>
         </result>
      </readMetadataResponse>
   </soapenv:Body>
</soapenv:Envelope>

Well, that isn't going to work. You get a nill <records xsi:nil="true"/> back for every full name you ask for. It doesn't actually matter if the fullName you provide corresponds to a valid flow or not.