After trying various things in various projects, here’s what has consistently worked best for me: an SQLite database file, containing data stored in YAML format, all of which data is read-only. (Modification is not allowed, because it would be impossible to keep all of the various persistent CGI-servers in sync.)
If you know that strings are likely to be used over and over again, especially in a persistent environment like mod_perl (or FastCGI), you might decide to maintain a small Cache (there are many flavors available, ready-made ...). But the principle is the same: most of the data is kept on disk, and demand-loaded, with a reasonable and adjustable cap on the number of entries that are allowed to be in memory at once.
I specified YAML because I have had “unexpected problems” that I could never quite explain with Storable. (I’d store stuff and then be unable to get it back.) So, I use this format, which also has the big advantage of being human-readable. Note also that I am rarely dealing with “every microsecond counts” performance-laden situations, so Your Mileage May Vary.™