Well, I'm actually surprised to hear that the computers that you are going to be dealing with don't have CD burners.. get with the 90's already!

(joke)
More seriously though, what about those mini CD-RWs? If you kept them in a case while not being used, they would be protected, and the disc+case would be about the same size as a 3.5in floppy. They store about 185MB or so worth of data. (The round mini-CDRWs, not the rectangular business-card-sized ones.)
As far as reliability goes, I know, CD-RW isn't too good, but during heavy usage, I'm not sure that the flash drives would fare all that much better. The only reason that I keep bringing this up, is that yours seems to be a cost-sensitive application, and I'm not sure that you will be able to find cheap enough flash drives to meet your specs. I'd almost suggest that magneto-optical might be a better solution, but given how uncommon they are today, and most had a SCSI interface, etc., that really simply wouldn't be feasable. I'm also going to go out on a limb here and assume that you don't control all of the machines that you need to interoperate with, so upgrading the lacking machines with cheap IDE CD-RW drives is likely not an option. Otherwise, I would go that route, since the cost of a new CD-RW drive is barely any more than a 64/128MB flash drive is.
Here's a thought - what about contacting some of those places that do the logo-customized USB flash drives, and see if they have any production overruns or whatnot, that they might be willing to sell cheaper?