I submitted the following XML and got the expected results. The easiest way to figure out what is going on is to look at the XML.
<?xml version="1.0" encoding="utf-8"?>
<soap:Envelope xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/"
xmlns:t="http://schemas.microsoft.com/exchange/services/2006/types">
<soap:Header>
<t:RequestServerVersion Version="Exchange2010_SP2"/>
</soap:Header>
<soap:Body>
<FindItem xmlns="http://schemas.microsoft.com/exchange/services/2006/messages"
xmlns:t="http://schemas.microsoft.com/exchange/services/2006/types"
Traversal="Shallow">
<ItemShape>
<t:BaseShape>IdOnly</t:BaseShape>
</ItemShape>
<ParentFolderIds>
<t:DistinguishedFolderId Id="inbox"/>
</ParentFolderIds>
<QueryString>HasAttachments:true Subject:'ATTACHMENT TEST' Kind:email</QueryString>
</FindItem>
</soap:Body>
</soap:Envelope>