PhantomPhreak mentioned a couple of things a few pages back in the thread. Scanning through a 10 minute block quickly is not a problem and that this needs to be done only once per transaction. Subsequently this is available to the counterparty in its own db.