Question: I'm looking for a storage solution for small files that would be moved into a small sensor running arduino-like processor.

Ideally the single memory unit would be cheap (in 1-10 cents range), but the memory can be very limited (several megabytes).

The closest I've got so far is small SD Memory card, but the smallest 4GB ones cost several dollars (at least bought in quantities < 100). Anything else I should be looking at?

Answer: 
I assume that, if this is a cost sensitive item, you need a reliable supply of multiples (so looking for small SD cards on e-bay isn't a viable solution).

Does it need to be non-volatile storage? If it does't you may be able to find small 8-bit wide RAM chips at a pretty good price. If it needs to be non-volatile, you might look at individual flash chips. I found [this one](http://uk.rs-online.com/web/p/flash-memory-chips/8228473P/), an 8-bit by 512 KB Serial-SPI flash chip for £0.19 (about $0.28 US) in single units and £0.176 if you can by 100 at a time. I would expect DRAM chips and chips with a simpler interface to be less expensive (but you might end up spending more on interfacing the chips so it might end up as a wash).

If you're able to consider a variety of processor chips it might be worth looking for something that has adequate storage on chip. That might be the most cost effective way to get the space.
On ebay you can buy 2nd hand Nokia SD cards from old mobile phones which are 128MB or so and very cheap.