Why do I have the horrible, horrible feeling that you aren't entirely aware of what these people are/have been doing?
You just hit in the nail. We don't have an IT Security department. We detected them because they committed the error of asking the wrong questions, so made us wonder whay would they ask that, and we went through the logs, and found that they were using our systems in an unappropriate manner.

If they could carry out their "business operations" after a valid login with your existing system why would they go to all the trouble they have in order to to so?

If they couldn't carry out those "business operations" did they _ever_ request the ability to do so through proper channels and if they did how did the proper channels respond?
Basically this is the scenario. We have EXE files distributed to every desktop, and a web interface. They have their own web interface, so they requested us to provide them with Web Services, which we did. They said these WS were not responsive enough. Unfortunately they were right; we had an array of problems (mostly connectivity and firewall issues) which ultimately led to unresponsiveness of our Web Services.

People simply don't go through the amount of effort required to do what they have done for no reason. I can understand if they needed to do something that your system did not easily provide them and your company would not alter things - but then you would be aware of this partner's needs. It seems to me that you aren't and therefore it further seems to me that there is no pressing reason for this activity. That being the case this is malicious, probably criminal and I would block all access to your servers until further notice.
Well, they did presented complains about our services, and for some reason, everyone here was saying something like 'oh, this is not _my_ problem'; when I came across this thing, it was already burning, and they were already using our servers.

Since I was asked to 'solve' this, I was able to diagnose the problems and to perform corrective actions so our web services were up and running. Last friday near COB we received an email from them that stated that our web services were now reliable and they said the will use the proper channels from then on.

I myself don't trust them. I think that once they had the 'intention' of cracking our systems, they are not to be trusted, so I still have to think of ways of protect our systems, and I have to implement some Intrusion Detection System.

Also this was a very 'nice' warning that our systems are very insecure, and that we have to think seriously on how to secure our servers.

Thanks