You've commented out "seek" but you say using "sysseek" was a problem. "seek" will not work with syswrite, you must use sysseek. If you were using sysseek, how did it break things (i.e. compared to how they are broken without it)?
If you are going to sort the output anyway, one way of handling this might be to have each writer send output to it's own file, then concatenate/sort the files all at the same time at the end.
If you are writing output lines one at a time, you may be able to just open the file in append mode and write that way, without locks. I think this is OS/stdlib dependent so YMMV. UPDATE: Now that I think about it, this last suggestion just sounds bad. I forgot that I always use locks even in this case since there is no guarantee that the perl/OS/stdlib/whatever will support this in the future even on a machine I believe works this way today.