Here's an informative presentation about how HBase has (massively) sped up random access, as of version 0.20: http://www.docstoc.com/docs/7493304/HBase-Goes-Realtime
I did benchmarks on a previous version, and the results were pretty miserable (600ms/lookup on a table with several million columns). It certainly sounds like they've improved.