Email Service via Metadata API fails to create from Managed Package

It would appear that whatever mechanism is used behind EmailServicesFunction to verify the Apex class exists isn't taking into account Apex classes defined in an installed managed package.

As a possible work around try creating a wrapper Apex class in the subscriber org that extends your managed MYNS.EmailHandler class. Then configure EmailServicesFunction.apexClass to use this local namespace wrapper class. Yes, it is a bit of an ugly hack, but it might get things going while still allowing you to implement most of the handler code in the managed package.

---

While acknowledging that you want to automate all this from Apex. It might be worth trying the process manually with the UI via /email-admin/services/editEmailServicesFunction.apexp. I was able to select a managed Apex class in the UI. It didn't save because the the class didn't implement the Messaging.InboundEmailHandler interface, but it must have found the class to figure that out.

---

Finally, the SOAP version of EmailServicesFunction exposes ApexClassId. You could try the Partner SOAP API to create these record and use the more specific ID rather than the namespace and class name.

Expanding on this, I deployed the example class CreateTaskEmailExample that implements Messaging.InboundEmailHandler from Using the InboundEmail Object into my dev org. The resulting Apex class had the ID 01p0g000000KWccAAG.

Then with SOAP UI I POSTed the following to /services/Soap/u/36/00D700000000001:

Request

<soapenv:Envelope xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns:urn="urn:partner.soap.sforce.com" xmlns:urn1="urn:sobject.partner.soap.sforce.com">
   <soapenv:Header>
      <urn:SessionHeader>
         <urn:sessionId>00D700000000001!AQoAQGfuT.NotMyRealSessionId.Re2s3N2Ihtqfr</urn:sessionId>
      </urn:SessionHeader>
   </soapenv:Header>
   <soapenv:Body>
      <urn:create>
         <urn:sObjects>
            <urn1:type>EmailServicesFunction</urn1:type>
            <urn1:fieldsToNull></urn1:fieldsToNull>
            <urn1:ApexClassId>01p0g000000KWccAAG</urn1:ApexClassId>
            <urn1:FunctionName>CreateTaskEmailExample</urn1:FunctionName>
         </urn:sObjects>
      </urn:create>
   </soapenv:Body>
</soapenv:Envelope>

Response:

<soapenv:Envelope xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns="urn:partner.soap.sforce.com">
   <soapenv:Header>
      <LimitInfoHeader>
         <limitInfo>
            <current>314</current>
            <limit>15000</limit>
            <type>API REQUESTS</type>
         </limitInfo>
      </LimitInfoHeader>
   </soapenv:Header>
   <soapenv:Body>
      <createResponse>
         <result>
            <id>0910g000000L0m9AAC</id>
            <success>true</success>
         </result>
      </createResponse>
   </soapenv:Body>
</soapenv:Envelope>

So that worked solely with the Apex class ID and a FunctionName.

I was able to make the same callout directly from Apex:

string sessionId = UserInfo.getSessionId();
HttpRequest req = new HttpRequest();
req.setEndpoint(URL.getSalesforceBaseUrl().toExternalForm() + '/services/Soap/u/36.0');
req.setMethod('POST');
req.setHeader('Content-Type', 'text/xml; charset=UTF-8');
req.setHeader('SOAPAction', 'Wololo');
req.setBody('<?xml version="1.0" encoding="UTF-8"?><env:Envelope xmlns:env="http://schemas.xmlsoap.org/soap/envelope/" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:urn="urn:partner.soap.sforce.com" xmlns:urn1="urn:sobject.partner.soap.sforce.com"><env:Header><SessionHeader xmlns="urn:partner.soap.sforce.com"><sessionId>'+sessionId+'</sessionId></SessionHeader></env:Header><env:Body><urn:create><urn:sObjects><urn1:type>EmailServicesFunction</urn1:type><urn1:fieldsToNull></urn1:fieldsToNull><urn1:ApexClassId>01p0g000000KWccAAG</urn1:ApexClassId><urn1:FunctionName>CreateTaskEmailExample</urn1:FunctionName></urn:sObjects></urn:create></env:Body></env:Envelope>');
System.debug(req.getBody());
Http http = new Http();
HTTPResponse res = http.send(req);
System.debug(res.getBody());

That gave a successful response that showed the EmailServicesFunction record was created.

You could either directly parse the XML response in Apex, or use a tool to generated the Apex proxy classes for WebServiceCallout.invoke to do the SOAP calls for you. The FuseIT SFDC Explorer version of WSDL2Apex can do that for you if required, including just generating the required classes for that one method. (Disclaimer, this is a free tool from my current employer.)