DB_File works, but you do have to use flock and re-open the db each time to flush caches. MLDBM::Sync does this for you. I'm surprised MySQL didn't work for you. Did you run it on localhost and use localhost as the domain name when connecting? That tells it to use unix domain sockets which is much faster than using TCP sockets.

BerkeleyDB can definitely do what you want, but I would suggest you skip the multi-locking and just let it use a global lock. The performance you get from using it that way is good enough for nearly any perl use and it avoids deadlocking. There's some sample code using it this way in a benchmark script here.