A client can estimate the hashing power of a miner by looking at the payouts of newly generated blocks.
He can then send his transaction like normal, but get instant replies from miners.
If a miner decides to include the transaction in his next block he will send a signed version of the transaction - signed by the private key of his payout address + attach the public key
The client can listen for these "signed by miner" transactions, verify that the public key hashes to payout address and matches the sig, then estimate the total hashing power that "promised" to include his transaction in the next(or later) block

was this already suggested?
too tired to think of security holes right now