If you want I'll go shove a few GB into an mdbm, drop caches, and time a lookup.
2 seeks at the most, are you talking about a 32 bit address space? The only way that's possible in 64 bits is to direct map a hash into e.g. 2 32 bit chunks and use the hash as an actual disk block address for the first chunk, and an index into a block list for the 2nd chunk.
Not only that, we watched the bus on an SGI Challenge and counted cache misses and TBL misses. 2 TBL misses to get a key.
Saying that it isn't possible on a 64 bit VM system makes no sense to me. If I have a 2TB file and I seek to location A and read it, then seek to location B and read it, you are saying that's not possible? Same thing with mmap, I set a pointer to the mapping, read p, p += <number>, read p. Two seeks, two page faults, whatever you want to call it, it does 2 and only 2 I/O's to get a key/value (unless the pages are bigger than disk blocks but then those are going to be sequential I/O's, no extra seeks).
Anyway, I don't doubt that you can operate in 2 seeks in the normal case.