How about using DBD::XBase?

Granted, XBase lacks some functionality but is probably leaps and bounds ahead of an XML file or CSV file in terms of searchability. While it's not nearly as "full featured" as Access, it does handle simple SELECT/INSERT/UPDATE/DELETE statements.

The requirement of not having a database server makes things a little tough, but the XBase seems (to me, at least) to the closest to what you've described.

Good luck!