The first thought that comes to my mind is make your own custom binary format. For instance maybe separate your flat database into A..Z and compress each section individually. Or maybe place some sort of "binary markers" in your compressed file, then search for it and only open that "chunk". Or... maybe keep a second index file, detailing where in the main file, certain sections begin and end, and just SEEK them out.

You could get one of the compression modules off of cpan, and compress each record individually, then cat them together with a separator in between them. Basically you will end up with something like DBM.