Didn't Google use some kind of tape to store their data, even today in 2013?
Those are tape drives, which are great for backups. But they are unsuitable for anything else because they have insane seektimes
Well I am pretty sure it will be worth the wait considering the data will be just 30-40 bytes for a single key and not a lot more for 100 or 1000.