here is my idea (funny: I thought about this about one week before this thread was opened):
Use PC to generate a striped-down version of WikipediaXML file, if you want to. Only interesting this is the <page></page> and the <title></title> before that.
An all in one File is possible (because fopen only returns a pointer to fileposition; i think we can open a 2GB file on rockbox?)
next you need a table-file: Every record (in alphabetical position) and the desired fseek-Position (byte offset from beginning of datafile), so we can seek to that. And voila, we have our entry
The designthing of the wikipedia articles: tables and headlines are the most important thing. only a small interpreter is needed, but i'm not really able to code it.