The threads are completely distinct.  They are created by (and the code that
they execute is in) different instances of the same class.  They do not share
any variables, memory or any other resources.  The objects are initialized
with a "scenario" and then are set running in order to "solve" it (which can
take seconds, minutes or even hours depending on the scenario).  The
processing consists entirely of processing in memory.

The latest thought I have is that the problem is not due to the threading at
all but rather due to caching on the CPU (though I really have no idea about
the mechanics of caching - it's a wild guess).  The scenarios allocate lots
of relatively small amounts of memory during initialization.  Perhaps these
bits of memory are being fragmented in some cases and are messing up the
caching so that there are lots of cache misses, slowing down the processing.  
I'm currently working on allocating all of the memory in one block to see if
that has any effect.

My only other thought is that it's just a "feature" of the CPU or Win2K.  
I've noticed Visual Studio being affected by something similar.  Sometimes it
will seem to be running really slowly.  For example, selecting multiple lines
of text by scrolling down (using the down arrow) while holding the shift key
down is very slow; compiling takes longer than usual.  Once I shut VS down
and start it up again everything happens at normal speed.