Invested quite a few cycles on this issue last night.  The more time I 
spent on it, the more I became convinced that every single test working 
with sockets should be changed in one fell swoop in order to facilitate 
(virtually unlimited) parallel test execution without fear of port 
conflicts.

I've attached a second patch, trunk.2550-2.patch, which is my progress 
so far on doing just this.  The main changes can be expressed by the 
following two points:

a) do whatever it takes in network-oriented tests to ensure
   unique ports are obtained (relying on the bind_port() and
   find_unused_port() methods exposed by test_support)

b) never, ever, ever call SO_REUSEADDR on a socket from a test;
   because we're putting so much effort into obtaining a unique
   port, this should never be necessary -- in the rare cases that
   our attempts to obtain a unique port fail, then we absolutely
   should fail with EADDRINUSE, as the ability to obtain a unique
   port for the duration of a client/server test is an invariant
   that we *must* be able to depend upon.  If the invariant is
   broken, fail immediately (don't mask the problem with 
   SO_REUSEADDR).

With this patch applied, I can spawn a handful of Python processes and 
run the entire test suite (without -r, ensuring all tests are run in 
the same order, which should encourage port conflicts (if there were 
any)) without any errors*.  Doing that now is completely and utterly 
impossible.

[*] Well, almost without error.  All the I/O related tests that try and 
open @test fail.

I believe there's still outstanding work to do with this patch with 
regards to how the intracacies of SO_REUSEADDR and SO_EXCLUSIVEADDRUSE 
should be handled in the rest of the stdlib.  I'm still thinking about 
the best approach for this.  However, the patch as it currently stands 
is still quite substantial so I wanted to get it out sooner rather than 
later for review.

(I'll forward this to python-dev@ to try and encourage more eyes from 
people with far more network-fu than I.)