It's 'relatively' easy to hook a PIC into a large external flash card, be it a hard drive, CompactFlash, SecureDigital, (insert type here), card. For one example, www.sparkfun.com, search for the DOSonChip.
If I can do a PIC based MP3 player capable of running an 80GB laptop drive (along with a CF card used as a buffer) with about 12,000 mp3's on it with my own SLFS (silly little file system), you can surely do what you're talking about.
I suppose the problem would be in figuring out a decent method of indexing all of the data. Also, once you get a load of information loaded, I would think it might be a bit of a slow process of searching thru all that data with a PIC.