After a lot of discussions with developers that created the service, we concluded that there are some compatibility problems between .NET and Java.
Service developers made several changes on their side and at one moment, it started working on my side.