When you say "An external database is out of the question", does this mean that Berkely DB (and similar) cannot be used? They're pretty darn fast (compared to flat text files) and are easy to get your hands on, either included with Perl or on CPAN.
Update: Sorry, that's supposed to be spelled Berkeley (the wrong spelling won't help much if you try to do a search on it).