Edit
Thanks for the suggestions; to clarify, we already use SSL, but that doesn't generally authenticate the requesting party, merely the responding party (IIRC?). I'll look into the other ideas right away, thanks for the brainstorm!
Background
The organization I work for has a heterogeneous bunch of servers providing various services throughout the network. They're each written in their own idiosyncratic way and have their own protocols for querying and modifying data. Unsurprisingly, communication between these systems is constantly growing, and keeping everything in sync and able to communicate is getting harder. To improve maintainability, we want to switch to using web-services internally; this would help simply to improve maintainability to have some kind of portable, standardized data-interchange + messaging format. With more communication also comes the need to trust other servers and the messages they're sending.
Question
We have a bunch of servers offering interrelated services via web services (i.e. SOAP). All HTTP traffic is via SSL. How can the requesting servers ensure that they're talking to the right responding server? SSL by default authenticates the receiver to the sender. E.g. assume the network is hacked or someone wants to change some info (by calling a method) without authorization. How can we prevent such an agent from simply spoofing the sender?
WS-Security implementations from various vendors (say, .NET and java) don't seem to play nice with each other - in particular when services get more complicated (with stuff like transaction support), so that solution is unfortunately probably not a good one.
We have a (trusted) LDAP server against which users are authenticated; storing server authentications here is natural - but how? Having a username/password for a server is somewhat pointless, since if you need to send those to another server to authenticate yourself, that server might not be who it claims to be, and in any case, if it's hacked, it now can pretend to be you...
Perhaps we're missing an obvious solution, so I won't muddy the waters with our own ideas just yet - what would you do?