A step in the good direction already. I tried some German demo dictionaries and they worked with "Alice im Wunderland" (Thanks Netseeker for putting the book online!).
I then tried the German Duden dictionary also from Mobipocket.com and it runs perfect!
It's a big fat 30 mb dictionary but it's quite fast!
So the German and English ones are running but the French ones are still stubbornly refusing..