In my experience with a heavy load going on that is suffering performance problems (and there is no blocking to speak of) then having plenty of CPU and memory available means there is a very high probability of an IO bottleneck. 

I would like to point out that this issue has been going on for at LEAST a week now, possibly much more than that before you decided to post here. I know of a number of consultants that could identify the root cause of your issue(s) in less than an hour, almost guaranteed. Perhaps in a little as a few minutes. About 45 seconds is my record, and that was from a 2-minute profiler trace on a system I had never seen. It only took that long because I wanted to make sure that what I saw as soon as I opened the trace was the worst thing the app was doing. 😎

I also noticed that you did mention in your OP that there were "no disk IO constraints". Can you be specific about what that actually means? Did you measure IO stalls during the load event?

Another question: did this process EVER work acceptably for thousands of concurrent operations? If so the obvious question is what changed. If not, I refer you again to my comment about getting a consultant on board. I find it hard to understand why you would go round-and-round on a forum for so long while your system is taking up to 4 minutes to complete a tiny update.