The only solution I can think of would be to generate a random number (say between like 1 and 10,000 or something) and have they send that specific number of satoshis to a particular bitcoin address, and then send it back. That seems like a kind of "hacky" way of doing it though.
Why that and not a signed message from the address holding the coins?
In both cases you must have access to that address.
Indeed, sending a few satoshi to another address is not just "hacky" but lame.
Of course, it might also be possible that they are in cahoots with the actual owner of the address with the
BTC and that guy is just signing messages for a share of the loot:).