As far as I know, perl multithreading is still not ready for primetime. In any case, your description of the needs of the programs seems to argue against multithreading.

Fork/exec work fine in perl, on all platforms, although on NT they rely on some of those experimental threading features, so you could have problems there.

This sounds like a problem that's already been solved somewhere :) Unfortunately, a quick CPAN search didn't find anything that looks useful, apart from Proc::SyncExec.
--
Mike