Вы не говорите, какую технологию вы используете, поэтому я предполагаю, что это WCF. Вы не говорите, какую версию .NET вы используете на стороне службы, поэтому я предполагаю, что .NET 3.5 SP1.
Я рекомендую вам присмотреться. В частности, включите трассировку и посмотрите, что она говорит об этом. Запрос получен? В какой момент генерируется ответ? Возможно, служба найдена, но что-то не так с «действием» SOAP, так что эта вторая операция действительно не найдена. Помните, что то, что вы видите в веб-прокси, - это не то, что на самом деле запрашивает веб-прокси. Это должно быть, но может и не быть. Включите трассировку и узнайте.
Вы также можете рассмотреть возможность отладки службы, чтобы увидеть, была ли достигнута операция. Возможно, исключение в операции переводится на 404?
Кроме того, посмотрите в журналах событий, чтобы увидеть, произошло ли что-нибудь еще интересное примерно в то же время.