In a Virtual Enterprise (VE), the main functions of an IT infrastructure are: Virtual Enterprise formation; customer order tracking and monitoring; problem management (delays, re-configurations, re-routings). Formation and problem management implies complex interaction and we observed that in almost all interaction types, negotiation is essential. The structure of the VE IT system can be chosen to support negotiation. Our working system, called PROVE, is using a multi-agent architecture, where the agents are provided by a third trusted party, which we call Software Agent Common Provider (SACP). Agents can play various roles in this infrastructure. For negotiation processes, we are using Mediating agents. Mediation can be made fairer if the mediator agents have knowledge about the negotiating parties. Trust is the main concept related to this specific knowledge. Because trust is rather a vague concept, we identified some of the measurable values, which can quantify the level of trust the mediator has in one of the negotiating parties. In this paper, we propose some of these potential values, as the “tendency of exaggeration”, the “willingness to give in” and the “tendency to be ostracized by others”. We are showing how these values can be measured and continuously updated and used by the mediator agents. The paper concludes with arguments that mediated agent negotiation can enhance the processes of VE formation and problem management.