I had similar problems and awful random I/O performance (6 spindles, RAID5).

I could somewhat alleviate all this (up to ~130 random read/second)

You may read my notes

--
Nat