I started playing with DBD::SQLite. I imported 800,000 records into a db, and quickly realized that by default, most of my searches are indeed carried out as sequential searches, which makes them hopelessly slow. With FTS enabled, average lookup times fell from 4 seconds to 0.04 seconds. If this scales in a roughly linear fashion and I get 0.5 sec lookups on 10 million records, I'll be very happy with the speed.
Thanks again.