I believe the problem was that all of my ports were used up with
TIME_WAIT sockets and so it couldn't create more.  My test
case was similar to this:

Ah that's simple to solve then :- use more IP addresses and bind 
to them in RR in your user program.

Arguably the Linux TCP code should be able to do this by itself
when enough IP addresses are available, but it's not very hard
to do in user space using bind(2)

BTW it's also an very unusual case -- in most cases there are more
remote IP addresses

So, is there a better way to max out the connections per second without 
having to use tcp_tw_recycle?

Well did you profile where the bottle necks were?

Perhaps also just increase the memory allowed for TCP sockets.

-Andi