[Original complainer chiming in here] Thanks Chris & David for working on this. As it turns out, the problem was in a sense a case of PEBKAC -- we didn't realize that apt-sortpkgs existed! Now that we know that, the random ordering coming out of apt-ftparchive is no longer an issue for us... although one could argue that there is instead a documentation bug, in that apt-ftparchive(1) should say something along the lines of "packages will be listed in an unpredictable order; you may wish to run apt-sortpkgs to fix this".
Since the question of why we're using apt-ftparchive: For reasons of paranoia (we run an encrypted online backup service, so it's important to ensure that the binaries people are running are the right ones) we build packages and sign everything in a very locked-down environment. Using low level tools makes it possible to do exactly what we want under exactly the right conditions, in a way which isn't possible with a high level tool which does everything. -- Colin Percival Security Officer Emeritus, FreeBSD | The power to serve Founder, Tarsnap | www.tarsnap.com | Online backups for the truly paranoid