Stopping a multi-threaded windows service

This blog answer states that OnStop isn't called until all ThreadPool tasks complete, which is news to me but would explain your issue.

I've fielded many multi-threaded Windows Services but I prefer to create my own background threads rather than use the ThreadPool since these are long-running threads. I instantiate worker classes and launch their DoWork() method on the thread. I also prefer to use callbacks to the launching class to check for a stop signal and pass status rather than just test against a global variable.

You are missing memory barriers around accesses to StopService, which may be a problem if you have multiple CPUs. Better lock any reference object for ALL accesses to the shared variable. For example:

object @lock;

...

lock (@lock)
{
    StopService = true;
}

Edit: As another answer has revealed, this issue was not a locking problem, but I am leaving this answer here as a thing to check with multithread synchronization schemes.

Making the shared variable volatile would work in many cases as well, but it is more complex to prove correct because it does not emit full fences.