The answer to How to configure the web.config to allow requests of any length works fine.
Is there a way to change the limit for a specific service?
For example something like
<system.webServer>
<security>
<requestFiltering serviceName="MyService.asmx">//Only for 1 service
<requestLimits maxQueryString="32768"/>
</requestFiltering>
</security>
</system.webServer>