• Abstract the database IO functions into your own module that can be different for each platform (I know that DBI is fairly abstracted already, but I'm refering to something that will make both a dbm database (for example) (ala tie) and a SQL database (ala DBI) totally transparent to the application). You can then just use whichever module is appropriate for the system (including dynamicly useing it). This will allow you to optimize the db access for each system.
• Go with a straight dbm style database that will be the same everyplace.
• Use a flat-file style system that you control yourself. If I need something that *must* work on a system with just basic Perl installed, this is what I do. Very inefficient and slow but I have YET to have one not work someplace*.

Regardless of which you choose, it's ALWAYS a balance between compatibility and efficiency.

Good Luck!

* I write scripts that must be runnable anywhere, at anytime, without any "setting up" required. They must all be drop-and-run. Hell, I had a requirement not long ago that it needs to be runnable from this guy's iPaq :)