All facts indicate the problem _was_ the platform. The program ran much faster on Vista, even with the original manual threading. When ported to Linux with OpenMP the problem went away, suggesting it never really existed inside the program.