I know about undelete() from Enterprise API but it looks like only for records, anyway I tried it with request:
<?xml version="1.0" encoding="utf-8"?>
<soapenv:Envelope xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns:urn="urn:enterprise.soap.sforce.com">
<soapenv:Header>
<urn:SessionHeader>
<urn:sessionId>
00D28000001b4nTMwpuKlz
</urn:sessionId>
</urn:SessionHeader>
</soapenv:Header>
<soapenv:Body>
<urn:undelete>
<urn:ids>01I28000001HT0s</urn:ids>
<urn:ids>01I28000001aDre</urn:ids>
</urn:undelete>
</soapenv:Body>
</soapenv:Envelope>
and response is:
<?xml version="1.0" encoding="UTF-8"?>
<soapenv:Envelope xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns="urn:enterprise.soap.sforce.com">
<soapenv:Header>
<LimitInfoHeader>
<limitInfo>
<current>3917</current>
<limit>15000</limit>
<type>API REQUESTS</type>
</limitInfo>
</LimitInfoHeader>
</soapenv:Header>
<soapenv:Body>
<undeleteResponse>
<result>
<errors>
<message>Entity type is not undeletable</message>
<statusCode>CANNOT_INSERT_UPDATE_ACTIVATE_ENTITY</statusCode>
</errors>
<id>01I28000001HT0sEAG</id>
<success>false</success>
</result>
<result>
<errors>
<message>Entity type is not undeletable</message>
<statusCode>CANNOT_INSERT_UPDATE_ACTIVATE_ENTITY</statusCode>
</errors>
<id>01I28000001aDreEAE</id>
<success>false</success>
</result>
</undeleteResponse>
</soapenv:Body>
</soapenv:Envelope>