Вы должны быть в состоянии настроить время ожидания для объекта веб-службы - детали будут зависеть от того, какой именно класс он использует, но посмотрите на WebClientProtocol.Timeout
для примера.
Теперь вы можете либо вызвать это синхронно из выделенного потока, либо вы можете сделать асинхронный вызов веб-службы для начала, указав обратный вызов для выполнения (возможно, в потоке пула потоков) когда служба отвечает. В этом случае может оказаться, что вы можете указать время ожидания самого асинхронного вызова - опять же, это будет зависеть от того, какой именно класс прокси веб-службы у вас есть.
Таким образом, вам не нужно «тратить» поток, просто ожидая ответа - но вы можете обнаружить, что модель асинхронного программирования сложнее понять, чем синхронную. Если у вас есть только один или два из этих запросов одновременно, дополнительная пара потоков вряд ли будет проблемой. Если вы ждете ответов от 500 различных сервисов, это другой вопрос, и асинхронная модель определенно поможет.