К сожалению я не совсем понимаю, что именно Вы имеете в виду. Можно ли посмотреть кусок кода?

Берем

[System.Web.Services.Protocols.SoapRpcMethodAttribute("", RequestNamespace="http://services.APPserver.company.com", ResponseNamespace="http://services.APPserver.company.com", Use=System.Web.Services.Description.SoapBindingUse.Literal)]
[return: System.Xml.Serialization.XmlElementAttribute("loginReturn")]
public LoginResponse login(LoginRequest request) {
object[] results = this.Invoke("login", new object[] {
request});
return ((LoginResponse)(results[0]));
}

и начинаем эксперементировать. Для начала попробуем добавить в [return: XmlElementAttribute("...", Namespace = "http://services.APPserver.company.com")], т.к. есть подозрение, что сериализатор пытается найти эту шнягу в http://login.valueobjects.APPserver.company.com или в пустом просранстве имён. Если не поможет, попробуем заменить атрибут SoapRpcMethodAttribute на SoapDocumentMethodAttribute и смотрим, что получится.
Для того, чтобы понять, что ожидает сериализатор, создаем LoginResponse, заполняем его поля и отправляем на консоль с помошью обычного XmlSerializer-а (думаю, что не имеет смысла писать, как использовать XmlSerializer), сравниваем с ожидаемый результат с ответом сервера. Но тут надо учитывать, что XmlSerializer сериализует класс по правилам, определяемым только атрибутами класса (т.е. LoginResponse будет либо http://login.valueobjects.APPserver.company.com либо в пустом пространстве, не помню, как XmlType обрабатывается), а [return: XmlElementAttribute(...)] на методе прокси оказывает влияние на имя и пространство имён элемента.