What storage method? Data logging at 1000-4000 samples/sec

I've Googled and searched this subject for a while now and haven't come up with a good answer.

I want to use an ATMega328 to log data from the ADC at 1000-4000 samples/sec. (1-4 channels x ~1000hz each) This would appear possible, as I understand the ADC on the 328 can run at nearly 10,000 samples/sec.

The ADC will be called at regular intervals using a hardware timer interrupt, this is not a problem. Where I'm getting stuck is choosing a storage method that can absorb the constant stream of data from the ADC. At first I thought to use a SD card, but the best answer I read leaves me thinking I would have to write in blocks and possibly use another interrupt to trigger regular writes to the card while writing the streaming data to a buffer. (Likely the EEPROM)

I don't like this approach, because, as I understand, the EEPROM is only good for 100,000 write cycles and buffering and sending data adds complexity to the program. (Introducing possible errors and missed data)

Is there a better storage solution out there? I considered writing to an external EEPROM for a data dump later, but they have limited capacity. Ultimately I want the data written to a .txt file or similar so I can pull it into EXCEL and analyze the data later.

The OpenLog from Spark Fun seems to be pretty well optimized. It uses the double buffer approach to store to an SD card and is claimed to store serial data at 115200 baud. That would be about 800 lines of 15 ascii characters/second, but I have not tried recording data at that high a rate.

Try this super fast analog pin logger shows that it is possible to achieve 5000 samples a second with five analog inputs.