Кажется, что есть несоответствие между аннотацией в методе и тем, какое имя у вас есть в WSDL для имени поля во входном сообщении:
<portType name="MyService">
<operation name="Search">
<input message="tns:SearchRequest"/>
...
</operation>
</portType>
<message name="SearchRequest">
<part name="searchRequest" element="ans:AvailRQ"/>
</message>
Я бы попытался посмотреть фактический HTTP-трафик, передаваемый по проводам, чтобы увидеть, какое имя поля в сообщении SOAP наверняка.