Функция cookieless = AutoDetect работает путем отправки перенаправлений (302 или 403 IIRC) в браузер, чтобы определить, поддерживаются ли cookie.
Затем он устанавливает различные требуемые идентификаторы в URL-адресе, а не использует файлы cookie, если поддержка отсутствует.
Убедитесь, что метод, с которым вы тестируете веб-службу, поддерживает эти перенаправления и проверки, которые они выполняют для файлов cookie.
Если вы тестируете веб-сервис в Visual Studio, используя опцию Добавить веб-ссылку, то у VS есть известные проблемы с перенаправлениями, которые могут запутать воду.
В этом случае попробуйте изменить ссылку для настройки поддержки автоматического обнаружения файлов cookie:
http://<host>/<app>/<webservice>.asmx?wsdl&AspxAutoDetectCookieSupport=1