Maybe I'm missing something, but do in-order architectures even have much use for branch prediction? They can't speculatively execute based on the outcome of a conditional, right?
Sure they can. Branch prediction allows you to move an instruction along the pipeline before the instruction determining its outcome has been retired. Without branch prediction, every conditional jump will potentially stall the pipeline. With branch prediction, a correctly predicted branch executes quickly, and a mis-predicted branch results in a pipeline flush.
Instruction re-ordering is more about taking full advantage of multiple execution units (ALUs, etc.), or not completely stalling the pipeline to wait on a memory fetch.
Are they even out-of-order? I.e. is it Pentium or Pentium Pro class?