You tried BDB::Queue and it doesn't work for you? Is it not FIFO? Or just too undocumented?

There's not much that can compare in speed to BerkeleyDB. You could do something with a local copy of MySQL. That's about as fast it gets after BDB if you want a real database. You could also try hacking something on top of Cache::FastMmap, but it's a cache, not a database, and not built to be ACID.