When it comes to tracking down bugs in recently parallelized code look for static objects in the call path. This is a case where VB.NET’s naming convention makes it easier to realize this (in VB.NET static objects are called shared).
So far these have cropped up inside of basic data model objects (objects that correspond almost 1 to 1 to a real world object in the domain of your application). Usually it’s a performance optimization that Moore’s Law has made unnecessary. Apart from Moore’s Law object allocation in a managed context is pretty inexpensive.
In my case the culprits were a static Regex object and a static SoapFormatter.
When it comes to concurrency, not sharing (selfishness) is a virtue.