A further optimization would be to focus on what the mining pools 'see.'  Because pool miners work on the transaction data received by their pool operator, it should be relatively straight-forward to directly connect to pool operators in such a way as to see what transactions they have received.  Hashing power working on the merchant's transaction could therefore be roughly calculated.  Once a large majority of network hashing power is behind the merchant's transaction, the listening node processor could verify the transaction for the merchant.