+2  A: 

There is some throttle outside of WCF (a .Net or Windows thing) that defaults to only letting a maximum of two simultaneous outbound HTTP connections. Unfortunately I can't remember for the life of me the name of the thing (and what you'd put in app.config or your app to override it). Given that you're not seeing the requests leave the client, and that it's only HTTP, I think you're hitting "that thing". I'll keep looking for its name.

Update: Found it - try this on the client (but change the '2' to a bigger number):

<configuration>
  <system.net>
    <connectionManagement>
      <add address = "*" maxconnection = "2" />
    </connectionManagement>
  </system.net>
</configuration>
Brian
Unfortunately this didn't solve it... It changed the behaviour somewhat, but now all the requests seem to back up at the server
Orion Edwards
Updated my question with a timeline graph from fiddler which should hopefully help
Orion Edwards
A: 

I forget - could it be ordering? I think maybe RM over http preserves order but maybe Tcp sessions don't (unless you explicitly request it)? Is there an attribute on the Service Contract that described ordered/unordered sessions (I forget).

Brian
There is <reliableSession> which has an ordered attribute... I have it set to <reliableSession ordered="false" enabled="true" />
Orion Edwards
+1  A: 

If you change to BasicHttpBinding, does it work?

Is so, it sounds like this is your problem, Session throttling, something that bit me in the ass.

Serapth
+1  A: 

[Self-answer to show other users what our eventual solution was]

In the end, I never managed to solve this.
Our final solution was to switch our app away from WSHttpBinding and onto NetTcpBinding in production - we had been planning on doing this eventually anyway for performance reasons.

This is rather unfortunate though, as it leaves a black mark on WSHttpBinding which may or may not be warranted. If anyone does ever come up with a solution which does not involve ditching WSHttpBinding, I'd love to know about it

Orion Edwards
I think you shouldn't self-answer as actually we have no answer.Have you try to post bug to connect.microsoft.com ?
Shrike
Now that I've learnt a bit more about how things work, I think it may have been related to overloading the ThreadPool. If you queue lots of long-running operations to the threadpool, you get behaviour that looks almost exactly like this
Orion Edwards