I also posted to the perl5-porters list, and got a reply saying I do need to truncate the file.

I'm hoping to write a test-case today to get it to fail, and then implement the truncate to fix it.

I'll comment again if I am successful.

Were I writing it today, I probably wouldn't use Storable, but some kind of database, like SQLite.