I'm working on a proof-of-relay contract that pays out if and only if a given transaction hash has been mined. I imagine there is some kind of merkle proof that would make this possible?
You cannot make granular queries on transactions and their fields. There is a nice code summary of pyethapp here that shows what happens when a transaction is confirmed.
You'll find all variables that you have access to in solidity here. The visibility scope is only the last block (which contains the mined contract) meaning that you can't get data on previous and future blocks. That said you can still have a look at the transaction origin; if it is from an account that you expect to make a transaction and appears in the block chain in a non-local node (relative to the initiator of the transaction) then there is a chance that the transaction is going to be confirmed by multiple miners (it's a valid transaction).