Locking a DBM file in that manner is going to be problematic. You're always going to run into problems - starvation, for example, where a process ends up waiting a very long time for a lock to be freed, because you have no queue ordering.
Perhaps a solution to look up would be to have one 'thread' (fork, whatever ;) access the DBM file on behalf of the other processes: it could just lock the file, and then access it for the other threads, so immediately you gain from removing the startup cost of tieing the DBM. Another gain can then be made by 'queueing' requests - you could have an in-memory shared queue object, or perhaps a file FIFO. Obviously, you still need to lock access to this object, but since you'll be in and out of that object reasonably quickly it won't affect you as badly as something like a DBM file, and you also rule out problems like starvation.
Obviously, I'm simply outlining something which is actually fairly complicated, but generally the fork on request model doesn't work very well in terms of scaling. You more often see the helper-thread model, which tends to scale a bit better. Given only one process can have access to the file at a time, it makes much more sense to only have one process access it :) Having that process write the answer back to the client is fairly easy, and the helper threads would make sure all requests are queued in a timely fashion.
The other answer is to move to an RDBMS :o)