What language / stack does the community recommend for writing such a web service? I haven't written Java in a while (and it seems really old school :D). I need to be able to prototype this service quickly.
Then I would definitely recommend to use Java and the JAX-WS API which, like other Java EE 5 APIs, is annotation-based to ease the development. In other words, you annotate a Java class and voilà, you're done and can deploy it as web service. This is really perfect for prototyping (even if I would switch later to contract-first approach). For an implementation of this API, you can use the reference implementation (JAX-WS RI) which is included in Java 6 (since Java 6u4) and also used in Metro, the web service stack of GlassFish (Metro = JAX-WS RI + WSIT). Another (very good) stack which also implements JAX-WS is Apache CXF.
If you want some numbers about the performances of JAX-WS RI, have a look at this benchmark, it will give you an idea of its capabilities (and/or of the hardware you'll need).
And to get an idea of what this API looks like, have a look at Introducing JAX-WS 2.0 With the Java SE 6 Platform, Part 1 and Introducing JAX-WS 2.0 With the Java SE 6 Platform, Part 2 (the complexity may not be very representative of real life though).
Update: I've mentioned JAX-WS RI, Metro, Apache CXF and I would understand if you tell me that this is confusing. The problem is that if you google for JAX-WS, you'll meet all these terms/acronyms. So I tried to give the minimal informations to clarify what they are. If you need any clarification or more details, just let me know.