Buy more RAM.

Seriously, you should reconsider your prohibition against using an external database. At the very least, carefully consider following Hot Pastrami's advice and using Berkeley DB. It's very much worth the effort.

Depending on the nature of your lookups, it might be worth your while to memoize your data-accessing functions.