Transactional Replication - Replication Order of Related Tables
Looks like the pertinent part (in this case) was to ensure that both the parent and child tables are contained within a single publication; once we did this, then everything started to behave as it should, and 30 or 40 tests later we haven't seen any failures.

At a guess... this means that both tables' log entries will be read by the same log reader job on the distributor, and so will be read in the correct order. Having separate publications allows separate log reader jobs to run in parallel, leading to the situation we were seeing.